# Combination Sum - Backtracking / Dedup

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){
return;
}
if(target < 0) {
return;
}
for(int i = index; i < candidates.size(); 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 results``````

For 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, curr + [nums])
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){
return result;
}

if(sum > target){
return result;
}

for(int i=startIndex;i<candidates.size();i++){