Combination Sum

Medium

Python

def combination_sum(candidates,target):
    res=[]
    def bt(start,path,remaining):
        if remaining==0: res.append(path[:]); return
        for i in range(start,len(candidates)):
            if candidates[i]>remaining: break
            path.append(candidates[i])
            bt(i,path,remaining-candidates[i])
            path.pop()
    candidates.sort()
    bt(0,[],target)
    return res

Java

public List<List<Integer>> combinationSum(int[] candidates,int target){
    List<List<Integer>> res=new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(res,new ArrayList<>(),candidates,target,0);
    return res;
}
void backtrack(List<List<Integer>> res,List<Integer> path,int[] c,int rem,int start){
    if(rem==0){res.add(new ArrayList<>(path));return;}
    for(int i=start;i<c.length;i++){
        if(c[i]>rem) break;
        path.add(c[i]);
        backtrack(res,path,c,rem-c[i],i);
        path.remove(path.size()-1);
    }
}

Key Insight

Backtracking with pruning. Python nested function vs Java parameters.

Python → Java Differences

Nested function captures res
Java passes all as params
Pruning with break identical

Python

def combination_sum(candidates,target):
    res=[]
    def bt(start,path,remaining):
        if remaining==0: res.append(path[:]); return
        for i in range(start,len(candidates)):
            if candidates[i]>remaining: break
            path.append(candidates[i])
            bt(i,path,remaining-candidates[i])
            path.pop()
    candidates.sort()
    bt(0,[],target)
    return res

Java

public List<List<Integer>> combinationSum(int[] candidates,int target){
    List<List<Integer>> res=new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(res,new ArrayList<>(),candidates,target,0);
    return res;
}
void backtrack(List<List<Integer>> res,List<Integer> path,int[] c,int rem,int start){
    if(rem==0){res.add(new ArrayList<>(path));return;}
    for(int i=start;i<c.length;i++){
        if(c[i]>rem) break;
        path.add(c[i]);
        backtrack(res,path,c,rem-c[i],i);
        path.remove(path.size()-1);
    }
}

Algorithm Steps

1. Sort for pruning
2. Try each from start
3. Break if exceeds

← Previous All Backtracking Next →