- Problem Statement<\/a><\/li>
- Sample Test Cases :<\/a><\/li>
- Explanation 1:<\/a><\/li>
- Explanation 2:<\/a><\/li><\/ul><\/ul>
- Approach<\/a><\/li>
- C++ Code Implementation<\/a><\/li>
- Java Code Implementation<\/a><\/li>
- Python Code Implementation<\/a><\/li><\/ul>
- Practice Problem:<\/a><\/li>
- FAQs<\/a><\/li>
- Q.1: How could we have solved the problem if there were duplicates in the array?<\/a><\/li>
- Q.2: Why can\u2019t we use Dynamic Programming to solve this problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given an array, a[], <\/strong>consisting of distinct elements,<\/strong> and a target sum, <\/strong>find all the unique combinations in the array where the sum is equal to the target sum. <\/strong>The same number from the array may be chosen any<\/strong> number of times.<\/p>\n\n\n\n
Sample Test Cases :<\/span><\/h3>\n\n\n\n
Input 1:<\/strong><\/p>\n\n\n\n
a[] = [1, 2], sum = 4<\/p>\n\n\n\n
Output 1:<\/strong><\/p>\n\n\n\n[1, 1, 1, 1]\n\n\n\n[1, 1, 2]\n\n\n\n[2, 2]\n\n\n\n
Explanation 1:<\/h4>\n\n\n\n
All the possible combinations of elements that can sum up to sum<\/strong> are listed in the output.<\/p>\n\n\n\n
Input 2:<\/strong><\/p>\n\n\n\n
a[] = [1, 3, 4, 5, 6], sum = 4<\/p>\n\n\n\n
Output 2:<\/strong><\/p>\n\n\n\n[1, 1, 1, 1]\n\n\n\n[1, 3]\n\n\n\n[4]\n\n\n\n
Explanation 2:<\/h4>\n\n\n\n
All the possible combinations of elements that can sum up to sum<\/strong> are listed in the output.<\/p>\n\n\n\n
Approach<\/h2>\n\n\n\n
The approach to solving this problem is to use a naive backtracking-based recursive approach. The recursion will work based on the following choices when we are at the ith <\/strong>index:<\/p>\n\n\n\n
- Take the ith element into the set under consideration.<\/li>
- Do not take the ith element into the set under consideration.<\/li><\/ul>\n\n\n\n
Based on the states of the recursion, the algorithm is described as follows:<\/p>\n\n\n\n
Base Cases:<\/strong><\/p>\n\n\n\n
- If the sum<\/strong> == 0, at any moment in the recursive calls, we add that list to the result list and return from the function.<\/li>
- If the sum becomes negative or we reach the end of the array, we terminate that recursive call and return from that call.<\/li><\/ul>\n\n\n\n
Recursion:<\/strong><\/p>\n\n\n\n
- Insert the element at the current position into the list, and recurse for the value sum := sum – a[index].<\/strong> Now pop this element from the list, and recurse for sum := sum.<\/strong> These recursive transitions correspond to the choices listed above.<\/li><\/ul>\n\n\n\n
<\/figure>\n\n\n\n
Code \/ Implementation:<\/strong><\/p>\n\n\n\n
C++ Code Implementation<\/h3>\n\n\n\n
void getAllCombinationsUtil(vector < int > & a, int sum, int currIndex, vector < vector < int >> & result, vector < int > & curr) {\n if (sum == 0) {\n result.push_back(curr);\n return;\n } else if (sum < 0 || currIndex == (int) a.size()) {\n return;\n } else {\n curr.push_back(a[currIndex]);\n getAllCombinationsUtil(a, sum - a[currIndex], currIndex, result, curr);\n curr.pop_back();\n getAllCombinationsUtil(a, sum, currIndex + 1, result, curr);\n }\n}\nvector < vector < int >> getAllCombinations(vector < int > & a, int sum) {\n vector < vector < int >> result;\n vector < int > curr;\n int index = 0;\n getAllCombinationsUtil(a, sum, index, result, curr);\n return result;\n}<\/pre>\n\n\n\nJava Code Implementation<\/h3>\n\n\n\n
public static void getAllCombinationsUtil(int[] a, int sum, int currIndex, List < List < Integer >> result, List < Integer > curr) {\n if (sum == 0) {\n result.add(new ArrayList < > (curr));\n return;\n } else if (sum < 0 || currIndex == a.length) {\n return;\n } else {\n curr.add(a[currIndex]);\n getAllCombinationsUtil(a, sum - a[currIndex], currIndex, result, curr);\n curr.remove((int) curr.size() - 1);\n getAllCombinationsUtil(a, sum, currIndex + 1, result, curr);\n }\n}\npublic static List < List < Integer >> getAllCombinations(int[] a, int sum) {\n List < List < Integer >> result = new ArrayList < List < Integer >> ();\n List < Integer > curr = new ArrayList < > ();\n int index = 0;\n getAllCombinationsUtil(a, sum, index, result, curr);\n return result;\n}<\/pre>\n\n\n\nPython Code Implementation<\/h3>\n\n\n\n
def getCombinationsUtil(a, sum, currIndex, result, curr):\n if sum == 0:\n result.append(list(curr))\n return\n elif sum < 0 or currIndex == len(a):\n return\n else:\n curr.append(a[currIndex])\n getCombinationsUtil(a, sum - a[currIndex], currIndex, result, curr)\n curr.pop()\n getCombinationsUtil(a, sum, currIndex + 1, result, curr)\n\n\ndef getCombinations(a, sum):\n result = []\n curr = []\n index = 0\n getCombinationsUtil(a, sum, index, result, curr)\n return result<\/pre>\n\n\n\n
Complexity Analysis:<\/strong><\/p>\n\n\n\n
- If the sum becomes negative or we reach the end of the array, we terminate that recursive call and return from that call.<\/li><\/ul>\n\n\n\n
- If the sum<\/strong> == 0, at any moment in the recursive calls, we add that list to the result list and return from the function.<\/li>
- Q.2: Why can\u2019t we use Dynamic Programming to solve this problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code Implementation<\/a><\/li>
- Explanation 2:<\/a><\/li><\/ul><\/ul>
- Explanation 1:<\/a><\/li>
- Sample Test Cases :<\/a><\/li>
![\"Recursion](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Recursion-Tree-1-1024x640.png\")
<\/figure>\n\n\n\n