2018-08-13 LeetCode回溯算法(组合总和)总结

39. 组合总和
    candidates 中的数字可以无限制重复被选取

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if(candidates.length == 0 || candidates == null || target <= 0) return res;
        // 先将数组排序避免重复搜素
        Arrays.sort(candidates);
        helper(candidates, target, 0, new LinkedList<Integer>(), res);
        return res;
    }
    private void helper(int[] nums, int target, int index, List<Integer> tmp, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new LinkedList<Integer>(tmp));
            return;
        } else {
            // 选取之后的每个数字都是一种可能性
            for (int i = index; i < nums.length; i++) {
                if (target < nums[i] ){
                    return;
                }else{//DFS
                    tmp.add(nums[i]);
                    helper(nums, target - nums[i], i, tmp, res);
                    tmp.remove(tmp.size() - 1);
                }
            }
        }
    }    
}

40. 组合总和 II
    candidates 中的每个数字在每个组合中只能使用一次(递归调用时i+1)
    解集不能包含重复的组合(每个递归方法内部相等的值只加入一次)

if (i > index && nums[i] == nums[i - 1]) continue;

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

216. 组合总和 III
     找出所有相加之和为 n 的 k 个数的组合，组合中只含有 1 - 9 的正整数
     每种组合中不存在重复的数字(递归调用时i+1)

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if( n < 1 || k < 1) return res;
        helper(k, n, 1, new ArrayList<Integer>(), res);
        return res;
    }
    private void helper(int k, int n, int index, List<Integer> tmp, List<List<Integer>> res) {
        if(n == 0 && k == 0) {
            res.add(new ArrayList(tmp));
            return;
        } else if(n < 0 || k == 0) return;//k个数相加和小于n||不到k个数和已经大于n
        for(int i = index; i <= 9; i++) {
            tmp.add(i);
            helper(k - 1, n - i, i + 1, tmp, res);
            tmp.remove(tmp.size() - 1);
        }
    }
}

方法二

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if( n < 1 || k < 1) return res;
        helper(k, n, 1, new ArrayList<Integer>(), res);
        return res;
    }
    private void helper(int k, int n, int index, List<Integer> temp, List<List<Integer>> res) {
        if (k < temp.size()) {//k个数相加和小于n
                return;
            }
        if (n == 0 && temp.size() == k) {
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for (int i = index; i <= 9; i++) {
            if (n < i) {
                return;
            }
            temp.add(i);
            helper(k, n - i, i + 1, temp, res);
            temp.remove(temp.size() - 1);
      }
    }
}