Combination Sum
Program for Combination Sum
You are given an array of unique numbers nums and a target number target. Your goal is to find all unique combinations of numbers from nums that add up to target.
You can use the same number from nums as many times as needed. Two combinations are considered the same only if they use the same numbers with the same frequency.
The order of numbers in the combinations doesn’t matter, and you can return the combinations in any order.
Output: [[2,2,5],[9]]
Explanation:
- 2 + 2 + 5 = 9. We use 2 twice, and 5 once.
- 9 = 9. We use 9 once.
Output: [[3,3,3,3,4],[3,3,5,5],[4,4,4,4],[3,4,4,5]]
Output: []
Constraints:
- All elements of nums are distinct.
- 1 <= nums.length <= 20
- 2 <= nums[i] <= 30
- 2 <= target <= 30
Program for Combinational Sum
Recommendation for Time and Space Complexity –The ideal solution should have a time complexity of O(2^(t/m)) and a space complexity of O(t/m), where t is the target value and m is the smallest number in the array.
Hints for solving problems
Hint 1 :
Think of the problem as a decision tree, where at each step, you have n options (n is the size of the array). Each path in the tree represents a possible combination. To stop building a path, consider a base condition related to the target value.
Hint 2 :
Use backtracking to explore all possible paths. Keep a variable sum that tracks the total of the chosen numbers in the current path. If sum == target, save a copy of the current combination to the result. Think about how to implement this recursive process.
Hint 3 :
Start traversing the array from index i in each recursive step. For each step, try selecting elements from index i to the end of the array. Extend the current path only if adding the element keeps sum <= target. Save the current path to the result whenever the target is reached.
There are mainly 2 approach to solve this problem-
- Backtracking Method
- Backtracking(Optimal) Method
1. Backtracking Method
This approach explores all possible combinations by recursively adding numbers to a current path and checking if their sum equals the target. If the sum exceeds the target, the recursion stops (backtracks) and tries other numbers. It ensures all potential solutions are explored.
- Time complexity: O(2^(t/m))
- Space complexity: O(t/m)
where t is the given target and m is the minimum value in nums.
Code
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector& nums, int target) {
vector<int> cur;
backtrack(nums, target, cur, 0);
return res;
}
void backtrack(vector& nums, int target, vector<int>& cur, int i) {
if (target == 0) {
res.push_back(cur);
return;
}
if (target < 0 || i >= nums.size()) {
return;
}
cur.push_back(nums[i]);
backtrack(nums, target - nums[i], cur, i);
cur.pop_back();
backtrack(nums, target, cur, i + 1);
}
};
public class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum(int[] nums, int target) {
res = new ArrayList<List<Integer>>();
List<Integer> cur = new ArrayList();
backtrack(nums, target, cur, 0);
return res;
}
public void backtrack(int[] nums, int target, List cur, int i) {
if (target == 0) {
res.add(new ArrayList(cur));
return;
}
if (target < 0 || i >= nums.length) {
return;
}
cur.add(nums[i]);
backtrack(nums, target - nums[i], cur, i);
cur.remove(cur.size() - 1);
backtrack(nums, target, cur, i + 1);
}
}
class Solution:
def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
def dfs(i, cur, total):
if total == target:
res.append(cur.copy())
return
if i >= len(nums) or total > target:
return
cur.append(nums[i])
dfs(i, cur, total + nums[i])
cur.pop()
dfs(i + 1, cur, total)
dfs(0, [], 0)
return res
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @returns {number[][]}
*/
combinationSum(nums, target) {
let ans = [];
let cur = [];
this.backtrack(nums, target, ans, cur, 0);
return ans;
}
/**
* @param {number[]} nums
* @param {number} target
* @param {number[][]} ans
* @param {number[]} cur
* @param {number} index
*/
backtrack(nums, target, ans, cur, index) {
if (target === 0) {
ans.push([...cur]);
} else if (target < 0 || index >= nums.length) {
return;
} else {
cur.push(nums[index]);
this.backtrack(nums, target - nums[index], ans, cur, index);
cur.pop();
this.backtrack(nums, target, ans, cur, index + 1);
}
}
}
2. Backtracking(Optimal) Method
In this optimized approach, backtracking is enhanced by starting the recursive search only from the current index or later indices. This avoids duplicate combinations and reduces unnecessary computations, making the solution more efficient.
- Time complexity: O(2^(t/m))
- Space complexity: O(t/m)
Code
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector& nums, int target) {
sort(nums.begin(), nums.end());
dfs(0, {}, 0, nums, target);
return res;
}
void dfs(int i, vector<int> cur, int total, vector<int>& nums, int target) {
if (total == target) {
res.push_back(cur);
return;
}
for (int j = i; j < nums.size(); j++) { if (total + nums[j] > target) {
return;
}
cur.push_back(nums[j]);
dfs(j, cur, total + nums[j], nums, target);
cur.pop_back();
}
}
};
public class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum(int[] nums, int target) {
res = new ArrayList<>();
Arrays.sort(nums);
dfs(0, new ArrayList<>(), 0, nums, target);
return res;
}
private void dfs(int i, List cur, int total, int[] nums, int target) {
if (total == target) {
res.add(new ArrayList<>(cur));
return;
}
for (int j = i; j < nums.length; j++) { if (total + nums[j] > target) {
return;
}
cur.add(nums[j]);
dfs(j, cur, total + nums[j], nums, target);
cur.remove(cur.size() - 1);
}
}
}
class Solution:
def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
nums.sort()
def dfs(i, cur, total):
if total == target:
res.append(cur.copy())
return
for j in range(i, len(nums)):
if total + nums[j] > target:
return
cur.append(nums[j])
dfs(j, cur, total + nums[j])
cur.pop()
dfs(0, [], 0)
return res
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @returns {number[][]}
*/
combinationSum(nums, target) {
const res = [];
nums.sort((a, b) => a - b);
const dfs = (i, cur, total) => {
if (total === target) {
res.push([...cur]);
return;
}
for (let j = i; j < nums.length; j++) { if (total + nums[j] > target) {
return;
}
cur.push(nums[j]);
dfs(j, cur, total + nums[j]);
cur.pop();
}
};
dfs(0, [], 0);
return res;
}
}
