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 givenvoid 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 codeint 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 valueimport 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 valuedef 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 ansdef 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 Codearr = [2, 4, 6, 8]sum = 8ans = combinationSum(arr, sum)# If result is empty, thenif len(ans) <= 0: print("empty") # print all combinations stored in ansfor 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 approachusing 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 valuefunction 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 Codelet 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, thenif (ans.length == 0) { document.write("Empty");}// print all combinations stored in ansfor (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> |
Output
( 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
This article is contributed by Aditya Nihal Kumar Singh. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
