Print all non-increasing sequences of sum equal to a given number x - GeeksforGeeks

Print all non-increasing sequences of sum equal to a given number x - GeeksforGeeks
Given a number x, print all possible non-increasing sequences with sum equals to x.

The idea is to use a recursive function, an array arr[] to store all sequences one by one and an index variable curr_idx to store current next index in arr[]. 

//  Recursive Function to generate all non-increasing sequences

// with sum x

// arr[]    --> Elements of current sequence

// curr_sum --> Current Sum

// curr_idx --> Current index in arr[]

void generateUtil(int x, int arr[], int curr_sum, int curr_idx)

{

   // If current sum is equal to x, then we found a sequence

   if (curr_sum == x)

   {

      printArr(arr, curr_idx);

      return;

   }

 

   // Try placing all numbers from 1 to x-curr_sum at current index

   int num = 1;

 

   // The placed number must also be smaller than previously placed

   // numbers, i.e., arr[curr_idx-1] if there exists a pevious number

   while (num<=x-curr_sum && (curr_idx==0 || num<=arr[curr_idx-1]))

   {

       // Place number at curr_idx

       arr[curr_idx] = num;

 

       // Recur

       generateUtil(x, arr, curr_sum+num, curr_idx+1);

 

       // Try next number

       num++;

   }

}

 

// A wrapper over generateUtil()

void generate(int x)

{

    int arr[x]; // Array to store sequences on by one

    generateUtil(x, arr, 0, 0);

}

Read full article from Print all non-increasing sequences of sum equal to a given number x - GeeksforGeeks