Find all combinations that add upto given number - GeeksforGeeks
Given a positive number, find out all combinations of positive numbers that adds upto that number. The program should print only combinations, not permutations. For example, for input 3, either 1, 2 or 2, 1 should be printed.
Read full article from Find all combinations that add upto given number - GeeksforGeeks
Given a positive number, find out all combinations of positive numbers that adds upto that number. The program should print only combinations, not permutations. For example, for input 3, either 1, 2 or 2, 1 should be printed.
The idea is to use recursion. We use an array to store combinations and we recursively fill the array and recurse with reduced number. The invariant used in the solution is that each combination will always be stored in increasing order of elements involved. That way we can avoid printing permutations.
/* arr - array to store the combination index - next location in array num - given number reducedNum - reduced number */void findCombinationsUtil(int arr[], int index, int num, int reducedNum){ // Base condition if (reducedNum < 0) return; // If combination is found, print it if (reducedNum == 0) { for (int i = 0; i < index; i++) cout << arr[i] << " "; cout << endl; return; } // Find the previous number stored in arr[] // It helps in maintaining increasing order int prev = (index == 0)? 1 : arr[index-1]; // note loop starts from previous number // i.e. at array location index - 1 for (int k = prev; k <= num ; k++) { // next element of array is k arr[index] = k; // call recursively with reduced number findCombinationsUtil(arr, index + 1, num, reducedNum - k); }}/* Function to find out all combinations of positive numbers that add upto given number. It uses findCombinationsUtil() */void findCombinations(int n){ // array to store the combinations // It can contain max n elements int arr[n]; //find all combinations findCombinationsUtil(arr, 0, n, n);}