Print combinations of distinct numbers which add up to give sum N | C ++ implementation of the approach ; arr [ ] to store all the distinct elements index - next location in array num - given number reducedNum - reduced number ; Set to store all the distinct elements ; Base condition ; Iterate over all the elements and store it into the set ; Calculate the sum of all the elements of the set ; Compare whether the sum is equal to n or not , if it is equal to n print the numbers ; Find previous number stored in the array ; Store all the numbers recursively into the arr [ ] ; Function to find all the distinct combinations of n ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findCombinationsUtil ( int arr [ ] , int index , int n , int red_num ) { set < int > s ; int sum = 0 ; if ( red_num < 0 ) { return ; } if ( red_num == 0 ) { for ( int i = 0 ; i < index ; i ++ ) { s . insert ( arr [ i ] ) ; } for ( auto itr = s . begin ( ) ; itr != s . end ( ) ; itr ++ ) { sum = sum + ( * itr ) ; } if ( sum == n ) { for ( auto i = s . begin ( ) ; i != s . end ( ) ; i ++ ) { cout << * i << " ▁ " ; } cout << endl ; return ; } } int prev = ( index == 0 ) ? 1 : arr [ index - 1 ] ; for ( int k = prev ; k <= n ; k ++ ) { arr [ index ] = k ; findCombinationsUtil ( arr , index + 1 , n , red_num - k ) ; } } void findCombinations ( int n ) { int a [ n ] ; findCombinationsUtil ( a , 0 , n , n ) ; } int main ( ) { int n = 7 ; findCombinations ( n ) ; return 0 ; }