Dare2Solve
Given an array of distinct integers candidates
and a target integer target
, return a list of all unique combinations of candidates
where the chosen numbers sum to target
. You may return the combinations in any order. The same number may be chosen from candidates
an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The problem can be visualized as a tree where each node represents a choice of whether to include a candidate number in the current combination. By exploring all possible paths in this tree, we can find all unique combinations that sum up to the target.
Backtracking with Recursion:
temp
to store the current combination and a list ans
to store all valid combinations.Recursive Function:
Start the Recursion:
O(2^n), where n is the length of the candidates array. This is because, in the worst case, we might have to explore all possible combinations.
O(target/min(candidates)), where min(candidates) is the smallest number in the candidates array. This accounts for the maximum depth of the recursion tree and the space needed to store the current combination.
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> output;
set<vector<int>> uniqueCombinations;
function<void(vector<int>, int)> recursion = [&](vector<int> currArr, int currTarget) {
if (currTarget == 0) {
vector<int> sortedCurrArr = currArr;
sort(sortedCurrArr.begin(), sortedCurrArr.end());
if (uniqueCombinations.find(sortedCurrArr) == uniqueCombinations.end()) {
uniqueCombinations.insert(sortedCurrArr);
output.push_back(sortedCurrArr);
}
return;
}
for (int num : candidates) {
if (currTarget - num >= 0) {
currArr.push_back(num);
recursion(currArr, currTarget - num);
currArr.pop_back(); // backtrack
}
}
};
recursion({}, target);
return output;
}
};
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
temp = []
self.find(candidates, 0, ans, temp, 0, target)
for combination in ans:
print(combination)
return ans
def find(self, nums: List[int], index: int, ans: List[List[int]], temp: List[int], sum: int, target: int):
if sum == target:
ans.append(temp.copy())
return
if sum > target or index == len(nums):
return
temp.append(nums[index])
self.find(nums, index, ans, temp, sum + nums[index], target)
temp.pop()
self.find(nums, index + 1, ans, temp, sum, target)
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
find(candidates, 0, ans, temp, 0, target);
for (List<Integer> no : ans) {
System.out.println(no);
}
return ans;
}
public void find(int[] nums, int index, List<List<Integer>> ans, List<Integer> temp, int sum, int target) {
if (sum == target) {
ans.add(new ArrayList<>(temp));
return;
}
if (sum > target || index == nums.length) {
return;
}
temp.add(nums[index]);
find(nums, index, ans, temp, sum + nums[index], target);
temp.remove(temp.size() - 1);
find(nums, index + 1, ans, temp, sum, target);
}
}
const combinationSum = function(candidates, target) {
const ans = [];
const temp = [];
const find = (nums, index, ans, temp, sum, target) => {
if (sum === target) {
ans.push([...temp]);
return;
}
if (sum > target || index === nums.length) {
return;
}
temp.push(nums[index]);
find(nums, index, ans, temp, sum + nums[index], target);
temp.pop();
find(nums, index + 1, ans, temp, sum, target);
};
find(candidates, 0, ans, temp, 0, target);
return ans;
};