Massive Algorithms: LeetCode 39

LeetCode 39 - Combination Sum

Related:
Subset Sum Problem - DP
LeetCode 39 - Combination Sum
LeetCode 40 - Combination Sum II
Leetcode 216 Combination Sum III
LeetCode 377 - Combination Sum IV
Given a set of candidate numbers C and a target number T, find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.

All numbers (including target) will be positive integers.
Elements in a combination $(a_1, a_2, \ldots, a_k)$ must be in non-descending order. (i.e., $a_1\leq a_2\leq \cdots \leq a_k$ ).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7, a solution set is: { [7], [2, 2, 3] }

基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的

Presort;
Optimization: exit early, branch
X. BFS

X. DP
https://discuss.leetcode.com/topic/8200/iterative-java-dp-solution

The main idea reminds an approach for solving coins/knapsack problem - to store the result for all i < target and create the solution from them. For that for each t from 1 to our target we try every candidate which is less or equal to t in ascending order. For each candidate "c" we run through all combinations for target t-c starting with the value greater or equal than c to avoid duplicates and store only ordered combinations.

I just wonder, would there be any relative performance disadvantage comparing to dfs when in cases where both the target and the candidates are large, e.g. target=1000000, candidates=[499999,500001]

    public List<List<Integer>> combinationSum(int[] cands, int t) {
        Arrays.sort(cands); // sort candidates to try them in asc order
        List<List<List<Integer>>> dp = new ArrayList<>();
        for (int i = 1; i <= t; i++) { // run through all targets from 1 to t
            List<List<Integer>> newList = new ArrayList(); // combs for curr i
            // run through all candidates <= i
            for (int j = 0; j < cands.length && cands[j] <= i; j++) {
                // special case when curr target is equal to curr candidate
                if (i == cands[j]) newList.add(Arrays.asList(cands[j]));
                // if current candidate is less than the target use prev results
                else for (List<Integer> l : dp.get(i-cands[j]-1)) {
                    if (cands[j] <= l.get(0)) {
                        List cl = new ArrayList<>();
                        cl.add(cands[j]); cl.addAll(l);
                        newList.add(cl);
                    }
                }
            }
            dp.add(newList);
        }
        return dp.get(t-1);
    }

X. DFS
https://discuss.leetcode.com/topic/46161/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning
https://discuss.leetcode.com/topic/7698/java-solution-using-recursive

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{ 
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}

Combination Sum II (can't reuse same element) : https://leetcode.com/problems/combination-sum-ii/

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
    
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{
        for(int i = start; i < nums.length; i++){
            if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i + 1);
            tempList.remove(tempList.size() - 1); 
        }
    }
}

http://codesniper.blogspot.com/2015/03/39-combination-sum-leetcode.html

1. base, terminating case:

if(target==0) ...

2. recursion steps:

a) try current candidate: items.add(candidate[i]);

b) recursion to next level: helper(target-candidate[i]...);

c) backtrack to current level, remove current candidate: items.remove(item.size()-1---> "candidate[i]")
Tips:
1. Skip duplicated elements to avoid non necessary recursion and duplicated result.
2. Since element can be used multi times, the next level will be start with the same index as the current level.

  public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> res=new ArrayList<List<Integer>>();  
     if(candidates==null || candidates.length==0) return res;  
     Arrays.sort(candidates);  
     List<Integer> item=new ArrayList<Integer>();  
     helper(candidates,0,target,item,res);  
     return res;  
   }  
   public void helper(int[] candidates, int index, int target, List<Integer> item, List<List<Integer>> res){  
     if(target==0){  
       List<Integer> temp= new ArrayList<Integer>(item);  
       res.add(temp);  
       return;  
     }  
     for(int i=index;i<candidates.length;i++){  
       if(i>0 && candidates[i]==candidates[i-1]) continue;  
        if(target-candidates[i]<0) return;  
       item.add(candidates[i]);  
       helper(candidates,i,target-candidates[i],item,res);  
       item.remove(item.size()-1);  
     }  
   }

http://bangbingsyb.blogspot.com/2014/11/leetcode-combination-sum-i-ii.html
由于candidates都为正数，当和超过或等于target时，查找中止。与3sum的思路一样，对candidate排序，并且每层递归扫描的时候需要做到去重复解：
1. 不回头扫，在扫描candidates[i]时，对candidate[i: n-1]递归查找target-candidates[i]。
2. 每层扫描的时候跳过重复的candidates。

public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if (candidates == null || candidates.length == 0)

            return result;

        Arrays.sort(candidates);        // Sort the candidate in non-descending order

        ArrayList<Integer> current = new ArrayList<Integer>();

        recursiveAppend(candidates, target, 0, current, result);

        return result;

}

    private void recursiveAppend(int[] candidates, int target, int startIndex, ArrayList<Integer> current,

                                 ArrayList<ArrayList<Integer>> result) {

        if (target < 0)

            return;

        if (target == 0) {     // The current array is an solution

            result.add(new ArrayList<Integer>(current));

            return;

}

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

            if (candidates[i] > target)    // No need to try the remaining candidates

                break;

            // Add candidate[i] to the current array

            current.add(candidates[i]);

            // Recursively append the current array to compose a solution

            recursiveAppend(candidates, target-candidates[i], i, current, result);

            // Remove candidate[i] from the current array, and try next candidate in the next loop

            current.remove(current.size()-1);

}

}

http://blog.csdn.net/linhuanmars/article/details/20828631
基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的.
注意在实现中for循环中第一步有一个判断，那个是为了去除重复元素产生重复结果的影响，因为在这里每个数可以重复使用，所以重复的元素也就没有作用了，所以应该跳过那层递归。
http://www.cnblogs.com/springfor/p/3884294.html

The same repeated number may be chosen from C unlimited number of times.

所以，每次跳进递归不用都往后挪一个，还可以利用当前的元素尝试。

同时，这道题还要判断重复解。用我之前介绍的两个方法：

1. if(i>0 && candidates[i] == candidates[i-1])//deal with dupicate
continue;

2. if(!res.contains(item))
res.add(new ArrayList<Integer>(item));

 1     public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {

 2         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

 3         ArrayList<Integer> item = new ArrayList<Integer>();

 4         if(candidates == null || candidates.length==0)

 5             return res;

 6    

 7         Arrays.sort(candidates);

 8         helper(candidates,target, 0, item ,res);

 9         return res;

10     }

11

12     private void helper(int[] candidates, int target, int start, ArrayList<Integer> item,

13     ArrayList<ArrayList<Integer>> res){

14         if(target<0)

15             return;

16         if(target==0){

17             res.add(new ArrayList<Integer>(item));

18             return;

19         }

20

21         for(int i=start;i<candidates.length;i++){

22             if(i>0 && candidates[i] == candidates[i-1])//deal with dupicate
23                 continue;

24             item.add(candidates[i]);

25             int newtarget = target - candidates[i];

26             helper(candidates,newtarget,i,item,res);//之所以不传i+1的原因是：27                                                     //The same repeated number may be 28                                                     //chosen from C unlimited number of times.
29             item.remove(item.size()-1);

30         }

31     }

http://www.jiuzhang.com/solutions/combination-sum/

// version 1: Remove duplicates & generate a new array
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return results;
        }
        
        int[] nums = removeDuplicates(candidates);
        
        dfs(nums, 0, new ArrayList<Integer>(), target, results);
        
        return results;
    }
    
    private int[] removeDuplicates(int[] candidates) {
        Arrays.sort(candidates);
        
        int index = 0;
        for (int i = 0; i < candidates.length; i++) {
            if (candidates[i] != candidates[index]) {
                candidates[++index] = candidates[i];
            }
        }
        
        int[] nums = new int[index + 1];
        for (int i = 0; i < index + 1; i++) {
            nums[i] = candidates[i];
        }
        
        return nums;
    }
    
    private void dfs(int[] nums,
                     int startIndex,
                     List<Integer> combination,
                     int remainTarget,
                     List<List<Integer>> results) {
        if (remainTarget == 0) {
            results.add(new ArrayList<Integer>(combination));
            return;
        }
        
        for (int i = startIndex; i < nums.length; i++) {
            if (remainTarget < nums[i]) {
                break;
            }
            combination.add(nums[i]);
            dfs(nums, i, combination, remainTarget - nums[i], results);
            combination.remove(combination.size() - 1);
        }
    }
}

// version 2: reuse candidates array
public class Solution {
    public  List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null) {
            return result;
        }

        List<Integer> combination = new ArrayList<>();
        Arrays.sort(candidates);
        helper(candidates, 0, target, combination, result);

        return result;
    }

     void helper(int[] candidates,
                 int index,
                 int target,
                 List<Integer> combination,
                 List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<Integer>(combination));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break;
            }

            if (i != index && candidates[i] == candidates[i - 1]) {
                continue;
            }

            combination.add(candidates[i]);
            helper(candidates, i, target - candidates[i], combination, result);
            combination.remove(combination.size() - 1);
        }
    }
}

    public  ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (candidates == null) {
            return result;
        }

        ArrayList<Integer> path = new ArrayList<Integer>();
        Arrays.sort(candidates);
        helper(candidates, target, path, 0, result);

        return result;
    }

     void helper(int[] candidates, int target, ArrayList<Integer> path, int index,
        ArrayList<ArrayList<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<Integer>(path));
            return;
        }

        int prev = -1; // use prev
        for (int i = index; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break;
            }

            if (prev != -1 && prev == candidates[i]) {
                continue;
            }

            path.add(candidates[i]);
            helper(candidates, target - candidates[i], path, i, result);
            path.remove(path.size() - 1);

            prev = candidates[i];
        }
    }

X. Iterative Version
https://leetcode.com/discuss/14362/dynamic-programming-solution
https://github.com/Deadbeef-ECE/Interview/blob/master/Leetcode/BackTracking/039_Combination_Sum.java
public List<List<Integer>> combinationSum(int[] nums, int target) {
if(nums == null || nums.length == 0)
return new LinkedList<List<Integer>>();
Arrays.sort(nums);
HashMap<Integer, List<List<Integer>>> dp = new HashMap<Integer, List<List<Integer>>>();
dp.put(0, new LinkedList<List<Integer>>());
dp.get(0).add(new LinkedList<Integer>());

for(int i = 0; i < nums.length; i++){ // skip when: nums[i[==nums[i+1]
int cur = nums[i];
for(int j = cur; j <= target; j++){//
if(dp.containsKey(j - cur)){//
for(List<Integer> sol : dp.get(j - cur)){
List<Integer> curSol = new LinkedList<Integer>(sol);
curSol.add(cur);
if(!dp.containsKey(j)){
dp.put(j, new LinkedList<List<Integer>>());
}
dp.get(j).add(curSol);
}
}
}
}
if(dp.get(target) == null)
return new LinkedList<List<Integer>>();
return dp.get(target);
}

https://leetcode.com/discuss/23818/iterative-java-dp-solution
thanks for this nice answer. I just wonder, would there be any relative performance disadvantage comparing to dfs when in cases where both the target and the candidates are large, e.g. target=1000000, candidates=[499999,500001]?

public List<List<Integer>> combinationSum(int[] cands, int t) { Arrays.sort(cands); // sort candidates to try them in asc order List<List<List<Integer>>> dp = new ArrayList<>(); for (int i = 1; i <= t; i++) { // run through all targets from 1 to t List<List<Integer>> newList = new ArrayList(); // combs for curr i // run through all candidates <= i for (int j = 0; j < cands.length && cands[j] <= i; j++) { // special case when curr target is equal to curr candidate if (i == cands[j]) newList.add(Arrays.asList(cands[j])); // if current candidate is less than the target use prev results else for (List<Integer> l : dp.get(i-cands[j]-1)) { if (cands[j] <= l.get(0)) { List cl = new ArrayList<>(); cl.add(cands[j]); cl.addAll(l); newList.add(cl); } } } dp.add(newList); } return dp.get(t-1); }
X. DFS Stack

   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Stack<SumNode> stack = new Stack<SumNode>();  
     Arrays.sort(candidates);  
     SumNode root = new SumNode(0, 0, new ArrayList<Integer>());  
     stack.push(root);  
     while(!stack.isEmpty()){  
       SumNode node = stack.pop();  
       for(int i = node.index;i < candidates.length;i++){  
         if(node.sum + candidates[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(candidates[i]);  
         if(child.sum==target) rslt.add(child.path);  
         else stack.push(child);  
       }  
     }  
     return rslt;  
   }

X. BFS Queue
http://siyang2leetcode.blogspot.com/2015/03/combination-sum.html

   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Queue<SumNode> queue = new LinkedList<SumNode>();  
     Arrays.sort(candidates);  
     SumNode root = new SumNode(0, 0, new ArrayList<Integer>());  
     queue.add(root);  
     while(!queue.isEmpty()){  
       SumNode node = queue.poll();  
       for(int i = node.index;i < candidates.length;i++){  
         if(node.sum + candidates[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(candidates[i]);  
         if(child.sum==target) rslt.add(child.path);  
         else queue.add(child);  
       }  
     }  
     return rslt;  
   }

X. Bad solutions
https://leetcode.com/discuss/10141/a-solution-avoid-using-set
public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> ret = new LinkedList<List<Integer>>(); Arrays.sort(candidates); // sort the candidates // collect possible candidates from small to large to eliminate duplicates, recurse(new ArrayList<Integer>(), target, candidates, 0, ret); return ret; } // the index here means we are allowed to choose candidates from that index private void recurse(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> ret) { if (target == 0) { ret.add(list); return; } for (int i = index; i < candidates.length; i++) { int newTarget = target - candidates[i]; if (newTarget >= 0) { List<Integer> copy = new ArrayList<Integer>(list); copy.add(candidates[i]);// add to list then remove it//backtrack recurse(copy, newTarget, candidates, i, ret); } else { break; } } }
https://leetcode.com/discuss/61491/asked-discuss-time-complexity-your-solution-what-would-say

(1) Let us see the difference between Combination Sum and Combination Sum II:
The input of Combination Sum has no dups, but each element can be used for MORE than one time.
The input of Combination Sum II has dups, but each element can be used for ONLY one time.

(2) Let us understand the time complexity of Combination Sum II at the beginning:
O(k * 2 ^ n) is the time complexity of Combination Sum II:
k is average length of each solution, and we need O(k) time to copy new linkedlist when we get one combination.

Solution space:
Since we use one element ONLY for one time, so, for the combinations with k elements, the number of different choices is C(n, k). And most of the time, this number is far smaller than k. But what is the worst case? int[] arr = {1,1,1,1,1,1,1,1,1}, target is 2, in this case, the number can actually reach C(n,k).

Considering that the combinations may have different length, which range from 0 ~ n. So, there are at most C(n,0) + C(n,1) + C(n,2) + ... C(n,n) solutions. We know that C(n,0) + C(n,1) + C(n,2) + ... C(n,n) = 2^n. Then we got the time complexity of Combination Sum II which is O(k * 2 ^ n).

(3) Then how we convert Combination Sum to Combination Sum II?
For example, given int[] arr = {2, 3, 4, 5, 6} and target is 10 and each element can be used for MORE than once.
Actually, it is same with the problem: given int[] arr = {2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6}, and target 10, each element can be used for ONLY one time, which is the same description of Combination Sum II.

And you must find that for the new array, each element E, which is smaller than target, will expand to ceil(target/E). Assume the new array has length n', we can get the time complexity which is O(k * 2 ^ n') using the same analysis of Combination Sum II.

https://github.com/Deadbeef-ECE/Interview/blob/master/Leetcode/BackTracking/039_Combination_Sum.java
// 此题time complexity无比蛋疼
// (1) 首先来看Combination sum I和II的区别:
// Combination sum 的input无dups, 但是input的元素可以重复利用
// Combination sum II 的input有重复, 但是input的元素只能用一次
//
// (2) 其次, 弄明白 Combination sum II的time complexity是怎么一回事儿
// https://github.com/Deadbeef-ECE/Interview/blob/master/Leetcode/BackTracking/040_Combination_Sum_II.java

// O(k * 2^n') time:
// 此题可以转换成 combination sum II, 如何做呢, 举个栗子:
// int[] arr = {2, 3, 4, 5, 6}, target = 10; 我们知道此题中,每个元素可以重复用,
// 其实, 如果把 arr 变成 {2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6}, 然
// 后每个元素只能用一次, 就变成了combination sum II的要求了.
// 我们再看新数组, 元素多了很多, 多了多少?
// 那就是数组中所有小于等于target的元素E增加了ceil(target/E)个, 然后就可以用
// combination sum II的方法分析复杂度了. 这里n'是新arr的大小

// O(n) space:
// one n is the recursion stack
// another n is used when copying list
// Both of them depend on the longest solution which is equal to
// target/(min in candidates) in this problem(可以再看下上面的例子, n就是新
// arr中2的个数, 为ceil(10/2))
Read full article from LeetCode - Combination Sum | Darren's Blog

LeetCode 39 - Combination Sum

Labels

Popular Posts