Print combinations of distinct numbers which add up to give sum N | Java 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
import java . util . * ; class GFG { static void findCombinationsUtil ( int arr [ ] , int index , int n , int red_num ) { HashSet < Integer > s = new HashSet < > ( ) ; int sum = 0 ; if ( red_num < 0 ) { return ; } if ( red_num == 0 ) { for ( int i = 0 ; i < index ; i ++ ) { s . add ( arr [ i ] ) ; } for ( Integer itr : s ) { sum = sum + itr ; } if ( sum == n ) { for ( Integer i : s ) { System . out . print ( i + " ▁ " ) ; } System . out . println ( ) ; return ; } } int prev = ( index == 0 ) ? 1 : arr [ index - 1 ] ; for ( int k = prev ; k <= n ; k ++ ) { if ( index < n ) { arr [ index ] = k ; findCombinationsUtil ( arr , index + 1 , n , red_num - k ) ; } } } static void findCombinations ( int n ) { int [ ] a = new int [ n ] ; findCombinationsUtil ( a , 0 , n , n ) ; } public static void main ( String arr [ ] ) { int n = 7 ; findCombinations ( n ) ; } }