Could you explain exactly why it is O(2^N)?
I don’t think this is 2^n runtime - Each call to the backtracking method iterates over the available candidates which is O(n), and the depth of calls to backtrack is O(T) where T = target sum. (i.e. if one of your candidates was 1, it would take T backtracking calls to get to the target sum). So runtime should be O(n^T)
The tests here are so bad, my incorrect solution passes all the tests, come on…
How does it pass?
def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
result = []
current = []
prev = None
def dfs(index, diff):
if diff == 0:
result.append(current[:])
if index == len(candidates) or diff <= 0:
return
for j in range(index, len(candidates)):
if candidates[j] == prev:
continue
current.append(candidates[j])
dfs(j, diff - current[-1])
current.pop()
dfs(0, target)
return result
better test your solution here https://leetcode.com/problems/combination-sum-ii/
pasted wrong link, this one is correct - https://leetcode.com/problems/combination-sum/
the solution is correct
leetcode
A simpler one?
def dfs(balance, path, path_max):
if balance == 0:
res.append(path); return
for c in candidates:
p = balance - c
if p >= 0 and c >= path_max:
dfs(p, path + [c], max(path_max, c))
res = []
dfs(target, [], 0)
return res
Clean Soloution
public static List<List<Integer>> combinationSum(List<Integer> candidates, int target) {
// WRITE YOUR BRILLIANT CODE HERE
List<List<Integer>> result = new ArrayList();
dfs(0,result,candidates,target, new ArrayList<Integer>());
return result;
}
private static void dfs(int index, List<List<Integer>> result, List<Integer> candidates, int target, List<Integer> current){
if(target == 0){
result.add(new ArrayList(current));
return;
}
if(target < 0) {
return;
}
for(int i = index; i < candidates.size(); i++){
current.add(candidates.get(i));
target -= candidates.get(i);
dfs(i, result,candidates,target,current);
target += candidates.get(i);
current.remove(current.size() - 1);
}
}
The runtime could be 2^n if the decision tree was done differently. If at each index you were to make a decision to use the number at that index as part of you current solution or decide not to then proceed to the next number.
for the time complexity, what is the n in O(n^target/min(candidates))?
Can you check my results please. The problem statements said “You may return the combinations in any order.” but seems like it is checking for the order.
#________________________________driver___________________________________#
def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
output = []
helper(candidates, target, 0, [], output)
return output
#__________________helper_________________#
def helper(nums, target, i, curr, output):
if target == 0:
output.append(curr[:])
return
if i >= len(nums):
return
num = nums[i]
max_num_count = target // num
for num_count in range(max_num_count + 1):
for _ in range(num_count):
curr.append(num)
target -= num
helper(nums, target, i + 1, curr, output)
for _ in range(num_count):
curr.pop()
target += num
Yes it is checking the order - my wacky code returns things in reverse order to the test cases. Manually verifying the result is good enough though 
def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
results = []
def backtrack(index, target, part):
if target == 0:
results.append(part)
return
if index == len(candidates):
return
backtrack(index + 1, target, part[:])
num = candidates[index]
while target - num >= 0:
target -= num
part.append(num)
backtrack(index + 1, target, part[:])
backtrack(0, target, [])
return resultsFor fun I tried again and this time my solution was way simpler…
def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
result = []
def backtrack(nums, target, curr):
if target == 0:
result.append(curr)
elif nums != [] and target > 0:
backtrack(nums, target - nums[0], curr + [nums[0]])
backtrack(nums[1:], target, curr)
backtrack(candidates, target, [])
return result
The posted solution assumes a sorted input. Note the condition : if (sum > target) break; Due to this condition, test cases such as [8,2,3,7], target=7 will not return any output with this solution.
Please mention this clearly in the problem statement.
right, you can always sort it first.
Simple Java solution
public static List<List> combinationSum(List candidates, int target) {
return dfs(candidates, target, new ArrayList<>(), new ArrayList<>(), 0, 0);
}
public static List<List<Integer>> dfs(List<Integer> candidates, int target,
List<List<Integer>> result, List<Integer> current, int sum, int startIndex){
if(sum == target){
result.add(new ArrayList<>(current));
return result;
}
if(sum > target){
return result;
}
for(int i=startIndex;i<candidates.size();i++){
current.add(candidates.get(i));
dfs(candidates, target, result, current, sum + candidates.get(i), i);
current.remove(current.size() - 1);
}
return result;
}
After saying “We dedup by only using candidate numbers whose index in the array is >= last used number’s index” - you should add the code snippet to represent that (for loop using value based on start parameter passed to dfs method). You only mention the pruning code snippet and its confusing.
Can we memoize here?