Combinational Sum
Given an array of positive integers arr[] and an integer x, The task is to find all unique combinations in arr[] where the sum is equal to x.
The same repeated number may be chosen from arr[] an unlimited number of times. Elements in a combination (a1, a2, …, ak) must be printed in non-descending order. (ie, a1 <= a2 <= … <= ak). If there is no combination possible print “Empty”.
Examples:
Input: arr[] = 2, 4, 6, 8, x = 8
Output:
[2, 2, 2, 2]
[2, 2, 4]
[2, 6]
[4, 4]
[8]
Approach:
Recursively find all combinations and if the current combination sums up to give X then add this combination in the final set of combinations.
Follow the below steps to implement the idea:
- Sort the array arr[] and remove all the duplicates from the arr[] then create a temporary vector r. to store every combination and a vector of vector res.
- Recursively follow:
- If at any time sub-problem sum == 0 then add that array to the res (vector of vectors).
- Run a while loop till the sum – arr[I] is not negative and i is less than arr.size().
- Push arr[i] in r and recursively call for i and sum-arr[i] ,then increment i by 1.
- pop r[i] from back and backtrack.
Below is the implementation of the above approach.
C++
// C++ program to find all combinations that // sum to a given value #include <bits/stdc++.h> using namespace std; // Print all members of ar[] that have given void findNumbers(vector< int >& ar, int sum, vector<vector< int > >& res, vector< int >& r, int i) { // if we get exact answer if (sum == 0) { res.push_back(r); return ; } // Recur for all remaining elements that // have value smaller than sum. while (i < ar.size() && sum - ar[i] >= 0) { // Till every element in the array starting // from i which can contribute to the sum r.push_back(ar[i]); // add them to list // recursive call for next numbers findNumbers(ar, sum - ar[i], res, r, i); i++; // Remove number from list (backtracking) r.pop_back(); } } // Returns all combinations // of ar[] that have given // sum. vector<vector< int > > combinationSum(vector< int >& ar, int sum) { // sort input array sort(ar.begin(), ar.end()); // remove duplicates ar.erase(unique(ar.begin(), ar.end()), ar.end()); vector< int > r; vector<vector< int > > res; findNumbers(ar, sum, res, r, 0); return res; } // Driver code int main() { vector< int > ar; ar.push_back(2); ar.push_back(4); ar.push_back(6); ar.push_back(8); int n = ar.size(); int sum = 8; // set value of sum vector<vector< int > > res = combinationSum(ar, sum); // If result is empty, then if (res.size() == 0) { cout << "Empty" ; return 0; } // Print all combinations stored in res. for ( int i = 0; i < res.size(); i++) { if (res[i].size() > 0) { cout << " ( " ; for ( int j = 0; j < res[i].size(); j++) cout << res[i][j] << " " ; cout << ")" ; } } return 0; } |
Java
// Java program to find all combinations that // sum to a given value import java.io.*; import java.util.*; class GFG { static ArrayList<ArrayList<Integer> > combinationSum(ArrayList<Integer> arr, int sum) { ArrayList<ArrayList<Integer> > ans = new ArrayList<>(); ArrayList<Integer> temp = new ArrayList<>(); // first do hashing since hashset does not always // sort // removing the duplicates using HashSet and // Sorting the arrayList Set<Integer> set = new HashSet<>(arr); arr.clear(); arr.addAll(set); Collections.sort(arr); findNumbers(ans, arr, sum, 0 , temp); return ans; } static void findNumbers(ArrayList<ArrayList<Integer> > ans, ArrayList<Integer> arr, int sum, int index, ArrayList<Integer> temp) { if (sum == 0 ) { // Adding deep copy of list to ans ans.add( new ArrayList<>(temp)); return ; } for ( int i = index; i < arr.size(); i++) { // checking that sum does not become negative if ((sum - arr.get(i)) >= 0 ) { // adding element which can contribute to // sum temp.add(arr.get(i)); findNumbers(ans, arr, sum - arr.get(i), i, temp); // removing element from list (backtracking) temp.remove(arr.get(i)); } } } // Driver Code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>(); arr.add( 2 ); arr.add( 4 ); arr.add( 6 ); arr.add( 8 ); int sum = 8 ; ArrayList<ArrayList<Integer> > ans = combinationSum(arr, sum); // If result is empty, then if (ans.size() == 0 ) { System.out.println( "Empty" ); return ; } // print all combinations stored in ans for ( int i = 0 ; i < ans.size(); i++) { System.out.print( "(" ); for ( int j = 0 ; j < ans.get(i).size(); j++) { System.out.print(ans.get(i).get(j) + " " ); } System.out.print( ") " ); } } } |
Python3
# Python3 program to find all combinations that # sum to a given value def combinationSum(arr, sum ): ans = [] temp = [] # first do hashing nothing but set{} # since set does not always sort # removing the duplicates using Set and # Sorting the List arr = sorted ( list ( set (arr))) findNumbers(ans, arr, temp, sum , 0 ) return ans def findNumbers(ans, arr, temp, sum , index): if ( sum = = 0 ): # Adding deep copy of list to ans ans.append( list (temp)) return # Iterate from index to len(arr) - 1 for i in range (index, len (arr)): # checking that sum does not become negative if ( sum - arr[i]) > = 0 : # adding element which can contribute to # sum temp.append(arr[i]) findNumbers(ans, arr, temp, sum - arr[i], i) # removing element from list (backtracking) temp.remove(arr[i]) # Driver Code arr = [ 2 , 4 , 6 , 8 ] sum = 8 ans = combinationSum(arr, sum ) # If result is empty, then if len (ans) < = 0 : print ( "empty" ) # print all combinations stored in ans for i in range ( len (ans)): print ( "(" , end = ' ' ) for j in range ( len (ans[i])): print ( str (ans[i][j]) + " " , end = ' ' ) print ( ")" , end = ' ' ) # This Code Is Contributed by Rakesh(vijayarigela09) |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Collections; class GFG { static List<List< int > > combinationSum(List< int > arr, int sum) { List<List< int > > ans = new List<List< int > >(); List< int > temp = new List< int >(); // first do hashing since hashset does not always // sort // removing the duplicates using HashSet and // Sorting the List HashSet< int > set = new HashSet< int >(arr); arr.Clear(); arr.AddRange( set ); arr.Sort(); findNumbers(ans, arr, sum, 0, temp); return ans; } static void findNumbers(List<List< int > > ans, List< int > arr, int sum, int index, List< int > temp) { if (sum == 0) { // Adding deep copy of list to ans ans.Add( new List< int >(temp)); return ; } for ( int i = index; i < arr.Count; i++) { // checking that sum does not become negative if ((sum - arr[i]) >= 0) { // Adding element which can contribute to // sum temp.Add(arr[i]); findNumbers(ans, arr, sum - arr[i], i, temp); // removing element from list (backtracking) temp.Remove(arr[i]); } } } // Driver Code public static void Main() { List< int > arr = new List< int >(); arr.Add(2); arr.Add(4); arr.Add(6); arr.Add(8); int sum = 8; List<List< int > > ans = combinationSum(arr, sum); // If result is empty, then if (ans.Count == 0) { Console.WriteLine( "Empty" ); return ; } // print all combinations stored in ans for ( int i = 0; i < ans.Count; i++) { Console.Write( "(" ); for ( int j = 0; j < ans[i].Count; j++) { Console.Write(ans[i][j] + " " ); } Console.Write( ") " ); } } } // This code is contributed by ShubhamSingh10 |
Javascript
<script> // Javascript program to find all combinations that // sum to a given value function combinationSum(arr, sum) { let ans = new Array(); let temp = new Array(); // first do hashing since hashset does not always // sort // removing the duplicates using HashSet and // Sorting the arrayList let set = new Set([...arr]); arr = [...set]; arr.sort() findNumbers(ans, arr, sum, 0, temp); return ans; } function findNumbers(ans, arr, sum, index, temp) { if (sum == 0) { // pushing deep copy of list to ans ans.push([...temp]); return ; } for (let i = index; i < arr.length; i++) { // checking that sum does not become negative if ((sum - arr[i]) >= 0) { // pushing element which can contribute to // sum temp.push(arr[i]); findNumbers(ans, arr, sum - arr[i], i, temp); // removing element from list (backtracking) temp.splice(temp.indexOf(arr[i]), 1); } } } // Driver Code let arr = [] arr.push(2); arr.push(4); arr.push(6); arr.push(8); let sum = 8; let ans = combinationSum(arr, sum); // If result is empty, then if (ans.length == 0) { document.write( "Empty" ); } // print all combinations stored in ans for (let i = 0; i < ans.length; i++) { document.write( "(" ); for (let j = 0; j < ans[i].length; j++) { document.write( " " , ans[i][j] + " " ); } document.write( ") " ); } // This code is contributed by saurabh_jaiswal. </script> |
( 2 2 2 2 ) ( 2 2 4 ) ( 2 6 ) ( 4 4 ) ( 8 )
Time Complexity: O(k*(2^n)) where n is the size of array, and k is average length
Auxiliary Space: O(k*x) where is x is number of possible combinations
Contact Us