39&40. 组合总和 I & II

回溯法，可先解答：

39. 组合总和

本题来自 LeetCode：39. 组合总和^[1]

题目描述

给定一个无重复元素的数组  candidates  和一个目标数  target ，找出  candidates  中所有可以使数字和为  target  的组合。
candidates  中的数字可以无限制重复被选取。
说明：
所有数字（包括  target）都是正整数。
解集不能包含重复的组合。 
示例  1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例  2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题目分析

常规的回溯法，要注意剪枝，否则可能会超时。

题目解答

class Solution {
    public ListListInteger combinationSum(int[] candidates, int target) {
        ListListInteger lists = new ArrayList();
        // 排序
        Arrays.sort(candidates);
        combinationSum(candidates, target, lists, new ArrayList(), 0);
        return lists;
    }

    public void combinationSum(int[] candidates,
                               int remaining,
                               ListListInteger lists,
                               ListInteger list,
                               int index) {
        // 满足条件，加入结果集
        if(remaining == 0) {
            lists.add(new ArrayList(list));
            return;
        }
        for(int i = index; i  candidates.length; i ++) {
            // 提前中止，剪枝
            if(remaining - candidates[i]  0) {
                break;
            }
            list.add(candidates[i]);
            combinationSum(candidates, remaining - candidates[i], lists, list, i);
            list.remove(list.size() - 1);
        }
    }
}

复杂度分析：
时间复杂度： O(2^n)
空间复杂度： O(n)

40. 组合总和 II

本题来自 LeetCode：40. 组合总和 II^[2]

题目描述

给定一个数组  candidates  和一个目标数  target ，找出  candidates  中所有可以使数字和为  target  的组合。
candidates  中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 
示例  1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例  2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

题目分析

参考的实现。

题目解答

class Solution {

    public ListListInteger combinationSum2(int[] candidates, int target) {
        ListListInteger lists = new LinkedList();
        Arrays.sort(candidates);
        combinationSum(candidates, target, lists, new LinkedList(), 0);
        return lists;
    }

    public void combinationSum(int[] candidates,
                               int remaining,
                               ListListInteger lists,
                               ListInteger list,
                               int index) {
        if(remaining == 0) {
            lists.add(new LinkedList(list));
            return;
        }
        // 这一步很关键，剪枝，大大减少运行用时
        if(index == candidates.length || remaining - candidates[index]  0) {
            return;
        }

        // 记录与candidates[index]相等的元素的个数
        int count = 0;
        while(count + index  candidates.length && candidates[count + index] == candidates[index]) {
            count ++;
        }

        // 不包含candidates[index]
        combinationSum(candidates, remaining, lists, list, index + count);

        // 包含candidates[index]的个数分别为1...count个
        for(int i = 1; i = count; i ++) {
            list.add(candidates[index]);
            remaining -= candidates[index];
            combinationSum(candidates, remaining, lists, list, index + count);
        }

        // 移除加入的count个candidates[index]元素
        for(int i = 1; i = count; i ++) {
            list.remove(list.size() - 1);
        }
    }
}

复杂度分析：
时间复杂度： O(2^n)， n个元素互不相同，退化成 39. 组合总和。
空间复杂度： O(n)，栈的深度最大为 n

参考资料

39. 组合总和: https://leetcode-cn.com/problems/combination-sum

40. 组合总和 II: https://leetcode-cn.com/problems/combination-sum-ii/

原文始发于微信公众号（xiaogan的技术博客）：