Print ways to obtain given sum by repeated throws of a dice - Coding

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 = 3

Input: 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 dice
void 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 Code
int main()
{
    int N = 3;
    printWays(N, "");
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public 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++) {
            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 Code
public 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 dice
def 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 Code
N = 3
printWays(N, "")
 
# This code is contributed by gfgking

C#

// C# program for the above approach
using 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

Time Complexity: O(6^N)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Backtracking

Related
Check if it’s possible to completely fill every container with same ball
Least count of words required to construct a target String
Count of permutations of an Array having each element as a multiple or a factor of its index
Generate all possible permutations of a Number divisible by N
Check if any King is unsafe on the Chessboard or not

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12