LeetCode39 . CombinationSum &

LeetCode39 . CombinationSum

题目---回溯题：

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

题目的大意是给定一个不重复数组和一个数，求数组中和为此数的所有组合（数可重复使用）。
代码贴上：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        return combination(candidates,target,0);
        
    }
    
    public List<List<Integer>> combination(int[] candidates,int target,int start) {
        List<List<Integer>> res  = new ArrayList<>();
        for(int i = start;i<candidates.length;i++){
            if(candidates[i]<target){
                //先求递归得目标数为target-candidates[i]的组合，再与candidates合并
                for(List<Integer> ar : combination(candidates,target-candidates[i],i)){ 
                    ar.add(0,candidates[i]);
                    res.add(ar);
                }
            }
            else if(candidates[i]==target){                //深搜的终止条件
                List<Integer> list= new ArrayList<>();
                list.add(target);
                res.add(list);
                
            }
            else
                break;
        }
        
        return res;
    }
}

解法采用了DFS的思想，在每一层将目标数转换为target-candidates[i]，直到target-candidates[i] == target 则一次搜索结束，然后就可进行回溯求得和为target的组合。

Leetcode40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

• Each number in candidates may only be used once in the combination.
• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

这道题只是对上面那道题做了点小改动：
1. 数组中有重复的数
2. 同一个数不能使用两次
解这道题的关键主要对上一题的解法做点小改动即可。即在进行循环时对于重复的数将它跳过

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        return combination(candidates,target,0);
        
    }
    
    public List<List<Integer>> combination(int[] candidates,int target,int start) {
        List<List<Integer>> res  = new ArrayList<>();
        for(int i = start;i<candidates.length;i++){
            if(i!=start&&candidates[i]==candidates[i-1])
                continue;
            if(candidates[i]<target){
                for(List<Integer> ar : combination(candidates,target-candidates[i],i+1)){
                        ar.add(0,candidates[i]);
                        res.add(ar);
                }
            }
            else if(candidates[i]==target){
                List<Integer> list= new ArrayList<>();
                list.add(target);
                res.add(list);
                
            }
            else
                break;
        }
        
        return res;
    }
}

核心代码是增加了一个判断其它不变

if(i!=start&&candidates[i]==candidates[i-1])
        continue;