39+40、Combination Sum、Combinatio

Combination Sum

For example, given candidate set 2,3,6,7 and target 7, A solution set
is: [7] [2, 2, 3]

解法

public class Solution{
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            List<Integer> temp = new ArrayList<Integer>();
            dfs(res, temp, target, candidates, 0);
            return res;
        }
        private static void dfs(List<List<Integer>> res, List<Integer> temp, int target,
                                int[] candidates, int j) {
            if(target == 0) {  //满足条件，将中间集加入结果集
                res.add(new ArrayList<Integer>(temp));
                return;
            }
            for(int i = j; i < candidates.length && target >= candidates[i]; i++) {  //target>=candidates[i]是剪枝操作
                if(i == j||candidates[i]!=candidates[i-1]){
                temp.add(candidates[i]);
                System.out.println(i+"\t"+j+"\t"+temp);
                dfs(res, temp, target - candidates[i], candidates, i);
                temp.remove(temp.size() - 1);}
            else{
                System.out.println("error:"+i+"\t"+j+"\t"+temp+"\t"+candidates[i]+"\t"+candidates[i-1]);
            }
        }
     }
}

Combination Sum 2

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6]

解法

 public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        Arrays.sort(candidates);
        findCandidates(candidates, target, 0, result, temp);
        return result;
    }
    public static void findCandidates(int[] candidates, int target, int curIndex, List<List<Integer>> result, List<Integer> temp) {
        if (0 == target) {
            result.add(new ArrayList<Integer>(temp));
        }
        for (int i = curIndex; i < candidates.length && candidates[i] <= target; i++) {
            if (i > curIndex && candidates[i] == candidates[i - 1]) continue; //去重
            temp.add(candidates[i]);
            System.out.println(temp);
            findCandidates(candidates, target - candidates[i], i + 1, result, temp);
            temp.remove(temp.size() - 1);
        }
    }