Given an integer N, the task is to print the ways to get the sum N by repeatedly throwing a dice.
Input: N = 3
Output:
1 1 1
1 2
2 1
3
Explanation: The standard dice has 6 faces i.e, {1, 2, 3, 4, 5, 6}. Therefore the ways of getting sum 3 after repeatedly throwing a dice are as follows:
1 + 1 + 1 = 3
1 + 2 = 3
2 + 1 = 3
3 = 3Input: N = 2
Output:
1 1
2
Approach: This problem can be solved by using Recursion and Backtracking. The idea is to iterate for every possible value of dice i in the range [1, 6] and recursively call for the remaining sum i.e, (N – i) and keep appending the value of the current dice value in a data structure like strings. If the required sum is zero, print the elements in the stored string.
Below is the implementation of the above approach
C++
// C++ program of the above approach#include <iostream>using namespace std;// Recursive function to print the// number of ways to get the sum// N with repeated throw of a dicevoid printWays(int n, string ans){ // Base Case if (n == 0) { // Print characters in // the string for (auto x : ans) { cout << x << " "; } cout << endl; return; } // If n is less than zero, // no sum is possible else if (n < 0) { return; } // Loop to iterate over all // the possible current moves for (int i = 1; i <= 6; i++) { // Recursive call for the // remaining sum considering // i as the current integer printWays(n - i, ans + to_string(i)); }}// Driver Codeint main(){ int N = 3; printWays(N, ""); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Recursive function to print the// number of ways to get the sum// N with repeated throw of a dicestatic void printWays(int n, String ans){ // Base Case if (n == 0) { // Print characters in // the string for (int i = 0; i < ans.length(); i++) { System.out.print(ans.charAt(i) + " "); } System.out.println(); return; } // If n is less than zero, // no sum is possible else if (n < 0) { return; } // Loop to iterate over all // the possible current moves for (int i = 1; i <= 6; i++) { // Recursive call for the // remaining sum considering // i as the current integer printWays(n - i, ans + Integer.toString(i)); }}// Driver Codepublic static void main(String args[]){ int N = 3; printWays(N, "");}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach# Recursive function to print the# number of ways to get the sum# N with repeated throw of a dicedef printWays(n, ans): # Base Case if n == 0: # Print characters in # the string for x in range(len(ans)): print(ans[x], end=" ") print("") return # If n is less than zero, # no sum is possible elif n < 0: return # Loop to iterate over all # the possible current moves for i in range(1, 7): # Recursive call for the # remaining sum considering # i as the current integer printWays(n - i, ans + str(i))# Driver CodeN = 3printWays(N, "")# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Collections;class GFG { // Recursive function to print the // number of ways to get the sum // N with repeated throw of a dice static void printWays(int n, string ans) { // Base Case if (n == 0) { // Print characters in // the string for (int i = 0; i < ans.Length; i++) { Console.Write(ans[i] + " "); } Console.WriteLine(); return; } // If n is less than zero, // no sum is possible else if (n < 0) { return; } // Loop to iterate over all // the possible current moves for (int i = 1; i <= 6; i++) { // Recursive call for the // remaining sum considering // i as the current integer printWays(n - i, ans + i.ToString()); } } // Driver Code public static void Main() { int N = 3; printWays(N, ""); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Recursive function to print the // number of ways to get the sum // N with repeated throw of a dice function printWays(n, ans) { // Base Case if (n == 0) { // Print characters in // the string for (let x = 0; x < ans.length; x++) { document.write(ans[x] + " "); } document.write('<br>') return; } // If n is less than zero, // no sum is possible else if (n < 0) { return; } // Loop to iterate over all // the possible current moves for (let i = 1; i <= 6; i++) { // Recursive call for the // remaining sum considering // i as the current integer printWays(n - i, ans + (i).toString()); } } // Driver Code let N = 3; printWays(N, "");// This code is contributed by Potta Lokesh </script> |
Output
1 1 1 1 2 2 1 3
Time Complexity: O(6N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
