Print all possible K-length subsequences of first N natural numbers with sum N

0 0 7 minutes read

Given two positive integers N and K, the task is to print all possible K-length subsequences from first N natural numbers whose sum of elements is equal to N.

Examples:

Input: N = 5, K = 3
Output: { {1, 1, 3}, {1, 2, 2}, {1, 3, 1}, {2, 1, 2}, {2, 2, 1}, {3, 1, 1} }
Explanation:
1 + 1 + 3 = N(= 5) and length is K(= 3)
1 + 2 + 2 = N(= 5) and length is K(= 3)
1 + 3 + 1 = N(= 5) and length is K(= 3)
2 + 1 + 2 = N(= 5) and length is K(= 3)
2 + 2 + 1 = N(= 5) and length is K(= 3)
3 + 1 + 1 = N(= 5) and length is K(= 3)

Input: N = 3, K = 3
Output: { {1, 1, 1} }

Approach: The problem can be solved using backtracking technique. Below is the recurrence relation:

$findSub(sum, K) = \sum_{i = 1}^{N}findSub(sum - i, K - 1)$

Follow the steps below to solve the problem:

Initialize a 2D array say, res[][] to store all possible subsequences of length K whose sum is equal to N.
Use the above recurrence relation and find all possible subsequences of length K whose sum is equal to N.
Finally, print the res[][] array.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print all subsequences of length
// K from N natural numbers whose sum equal to N
void findSub(vector<vector<int> >& res, int sum,
             int K, int N, vector<int>& temp)
{
 
    // Base case
    if (K == 0 && sum == 0) {
        res.push_back(temp);
        return;
    }
    if (sum <= 0 || K <= 0) {
        return;
    }
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // Insert i into temp
        temp.push_back(i);
        findSub(res, sum - i, K - 1, N, temp);
 
        // Pop i from temp
        temp.pop_back();
    }
}
 
// Utility function to print all subsequences
// of length K with sum equal to N
void UtilPrintSubsequncesOfKSumN(int N, int K)
{
 
    // Store all subsequences of length K
    // from N natural numbers
    vector<vector<int> > res;
 
    // Store current subsequence of
    // length K from N natural numbers
    vector<int> temp;
 
    findSub(res, N, K, N, temp);
 
    // Stores total count
    // of subsequences
    int sz = res.size();
 
    // Print all subsequences
    cout << "{ ";
 
    // Traverse all subsequences
    for (int i = 0; i < sz; i++) {
 
        cout << "{ ";
 
        // Print current subsequence
        for (int j = 0; j < K; j++) {
 
            // If current element is last
            // element of subsequence
            if (j == K - 1)
                cout << res[i][j] << " ";
            else
                cout << res[i][j] << ", ";
        }
 
        // If current subsequence is last
        // subsequence from n natural numbers
        if (i == sz - 1)
            cout << "}";
        else
            cout << "}, ";
    }
    cout << " }";
}
 
// Driver Code
int main()
{
 
    int N = 4;
    int K = 2;
    UtilPrintSubsequncesOfKSumN(N, K);
}

Java

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
 
class GFG {
 
  // Function to print all subsequences of length
  // K from N natural numbers whose sum equal to N
  static void findSub(List<List<Integer> > res, int sum,
                      int K, int N, List<Integer> temp)
  {
 
    // Base case
    if (K == 0 && sum == 0) {
      List<Integer> newList = temp.stream().collect(
        Collectors.toList());
      res.add(newList);
      return;
    }
    if (sum <= 0 || K <= 0) {
      return;
    }
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
      // Insert i into temp
      temp.add(i);
      findSub(res, sum - i, K - 1, N, temp);
 
      // Pop i from temp
      temp.remove(temp.size() - 1);
    }
  }
 
  // Utility function to print all subsequences
  // of length K with sum equal to N
  static void UtilPrintSubsequncesOfKSumN(int N, int K)
  {
 
    // Store all subsequences of length K
    // from N natural numbers
    @SuppressWarnings("unchecked")
    List<List<Integer> > res = new ArrayList();
 
    // Store current subsequence of
    // length K from N natural numbers
    @SuppressWarnings("unchecked")
    List<Integer> temp = new ArrayList();
 
    findSub(res, N, K, N, temp);
 
    // Stores total count
    // of subsequences
    int sz = res.size();
 
    // Print all subsequences
    System.out.print("{ ");
 
    // Traverse all subsequences
    for (int i = 0; i < sz; i++) {
 
      System.out.print("{ ");
 
      // Print current subsequence
      for (int j = 0; j < K; j++) {
 
        // If current element is last
        // element of subsequence
        if (j == K - 1)
          System.out.print(res.get(i).get(j)
                           + " ");
        else
          System.out.print(res.get(i).get(j)
                           + ", ");
      }
 
      // If current subsequence is last
      // subsequence from n natural numbers
      if (i == sz - 1)
        System.out.print("}");
      else
        System.out.print("}, ");
    }
    System.out.print(" }");
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 4;
    int K = 2;
    UtilPrintSubsequncesOfKSumN(N, K);
  }
}
 
// This code is contributed by jithin.

Python3

# Python program to implement
# the above approach
 
 
# Function to print all subsequences of length
# K from N natural numbers whose sum equal to N
def findSub(res,sum,K,N,temp):
 
    # Base case
    if (K == 0 and sum == 0):
        res.append(temp[:])
        return
 
    if (sum <= 0 or K <= 0):
        return
 
    # Iterate over the range [1, N]
    for i in range(1,N):
 
        # Insert i into temp
        temp.append(i)
        findSub(res, sum - i, K - 1, N, temp)
 
        # Pop i from temp
        temp.pop()
 
# Utility function to print all subsequences
# of length K with sum equal to N
def UtilPrintSubsequncesOfKSumN(N, K):
 
    # Store all subsequences of length K
    # from N natural numbers
    res = []
 
    # Store current subsequence of
    # length K from N natural numbers
    temp = []
 
    findSub(res, N, K, N, temp)
     
    # # Stores total count
    # # of subsequences
    sz = len(res)
 
    # Print all subsequences
    print("{",end=" ")
 
    # Traverse all subsequences
    for i in range(sz):
 
        print("{",end=" ")
 
        # Print current subsequence
        for j in range(K):
 
            # If current element is last
            # element of subsequence
            if (j == K - 1):
                print(res[i][j],end=" ")
            else:
                print(res[i][j],end = ", ")
 
        # If current subsequence is last
        # subsequence from n natural numbers
        if (i == sz - 1):
            print("}",end="")
        else:
            print("},",end =" ")
    print(" }")
 
# Driver Code
N = 4
K = 2
UtilPrintSubsequncesOfKSumN(N, K)
 
# This code is contributed by shinjanpatra

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace GFG {
  class Program {
    // Function to print all subsequences of length
    // K from N natural numbers whose sum equal to N
    static void FindSub(List<List<int> > res, int sum,
                        int K, int N, List<int> temp)
    {
      // Base case
      if (K == 0 && sum == 0) {
        List<int> newList = temp.ToList();
        res.Add(newList);
        return;
      }
      if (sum <= 0 || K <= 0) {
        return;
      }
 
      // Iterate over the range [1, N]
      for (int i = 1; i <= N; i++) {
        // Insert i into temp
        temp.Add(i);
        FindSub(res, sum - i, K - 1, N, temp);
 
        // Pop i from temp
        temp.RemoveAt(temp.Count - 1);
      }
    }
 
    // Utility function to print all subsequences
    // of length K with sum equal to N
    static void UtilPrintSubsequncesOfKSumN(int N, int K)
    {
      // Store all subsequences of length K
      // from N natural numbers
      var res = new List<List<int> >();
 
      // Store current subsequence of
      // length K from N natural numbers
      var temp = new List<int>();
 
      FindSub(res, N, K, N, temp);
 
      // Stores total count
      // of subsequences
      int sz = res.Count;
 
      // Print all subsequences
      Console.Write("{ ");
 
      // Traverse all subsequences
      for (int i = 0; i < sz; i++) {
        Console.Write("{ ");
 
        // Print current subsequence
        for (int j = 0; j < K; j++) {
          // If current element is last
          // element of subsequence
          if (j == K - 1)
            Console.Write(res[i][j] + " ");
          else
            Console.Write(res[i][j] + ", ");
        }
 
        // If current subsequence is last
        // subsequence from n natural numbers
        if (i == sz - 1)
          Console.Write("}");
        else
          Console.Write("}, ");
      }
      Console.WriteLine(" }");
    }
 
    static void Main(string[] args)
    {
      int N = 4;
      int K = 2;
      UtilPrintSubsequncesOfKSumN(N, K);
    }
  }
 
}
 
// This code is contributed by phasing17.

Javascript

// Python program to implement
// the above approach
 
 
// Function to print all subsequences of length
// K from N natural numbers whose sum equal to N
function findSub(res,sum,K,N,temp)
{
    // Base case
    if (K == 0 && sum == 0)
    {
        res.push([...temp])
        return
    }
     
    if (sum <= 0||K <= 0)
        return
 
    // Iterate over the range [1, N]
    for (var i = 1; i < N; i++)
    {
        // Insert i into temp
        temp.push(i)
        findSub(res, sum - i, K - 1, N, temp)
 
        // Pop i from temp
        temp.pop()
    }
}
// Utility function to print all subsequences
// of length K with sum equal to N
function UtilPrintSubsequncesOfKSumN(N, K)
{
    // Store all subsequences of length K
    // from N natural numbers
    let res = []
 
    // Store current subsequence of
    // length K from N natural numbers
    let temp = []
 
    findSub(res, N, K, N, temp)
     
    // // Stores total count
    // // of subsequences
    let sz = res.length
     
 
    // Print all subsequences
    process.stdout.write("{"+" ")
 
    // Traverse all subsequences
    for (var i = 0; i < sz; i++)
    {
        process.stdout.write("{"+" ")
 
        // Print current subsequence
        for (var j = 0; j < K; j++)
        {
            // If current element is last
            // element of subsequence
            if (j == K - 1)
                process.stdout.write(res[i][j]+" ")
            else
                process.stdout.write(res[i][j] + ", ")
        }
 
        // If current subsequence is last
        // subsequence from n natural numbers
        if (i == sz - 1)
            process.stdout.write("}"+"")
        else
            process.stdout.write("}," + " ")
    }
    process.stdout.write(" }")
}
 
// Driver Code
let N = 4
let K = 2
UtilPrintSubsequncesOfKSumN(N, K)
 
// This code is contributed by phasing17

Output:

{ { 1, 3 }, { 2, 2 }, { 3, 1 } }

Time Complexity: O(2^N)
Auxiliary Space: O(X), where X denotes the count of subsequences of length K whose sum is N

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 zambiatek!