0%

[0040] 组合总和 II

发表于 更新于 分类于 ， 本文字数： 2.6k 阅读时长 ≈ 2 分钟
...

[0040] 组合总和 II

题目描述

给定一个数组 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]
]

Related Topics
  • 数组
  • 回溯算法

    • 题目解析

    • 集合选取法
    • 暴力搜索+剪枝

    不确定性

    • 给定target的范围
    • 数据长度以及元素范围

    方法一：集合选取法

    分析

    • 对于一个数字来讲就是选取或者不选取，穷举出所有可能依次判断即可
    • 这里要解决的一个问题是相同的数字有可能被多选，举例[1, 1], 子集中会有2个[1] 这种情况是要去重。
    • 注意剪枝

    思路

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    基本思路
    subSet(dep, candidates, res, selected, left) :
    	if 0 == left: 
    		res.push(selected)
    		return
    	
    	if left<0: return
    	if dep >= len(candidates): return
    	
    	// 不选取当前数字
    	subSet(dep+1, candidates, res, selected, left)
    	
    	// 选取当前数字
    	selected.push(candidates[dep])
    	subSet(dep+1, candidates, res, selected, left-candidates[dep])
    	selected.pop()
    	
    	return
    	
    优化去重逻辑：
    假设 [a,b,c] = [1,1,2]
    选取过程如下：
    [a], [a，b], [a，b，c], [a,c], [b], [b,c](这里已经重复了), [c]
    从上面过程中可以看出，选b的时候前面有一个和b相同的元素还没有被选择过说明这个时候还轮不到b来选。

    // 优化后 先对candidates排序
    subUniqueSet(dep, candidates, res, selected, left) :
    	if 0 == left: 
    		res.push(selected)
    		return
    	
    	if left<0: return
    	if dep >= len(candidates): return
    	
    	
    	// 不选取当前数字
    	subSet(dep+1, candidates, res, selected, left)
    	
    	// 选取当前数字
    	// 判断是否前面有相同数字没有被选择
    	if dep>0 && candidates[dep-1]==candidates[dep]: return
    	curnum = candidates[dep]
    	selected.push(curnum)
    	candidates[dep]=-1 //标记被选中了
    	subSet(dep+1, candidates, res, selected, left-curnum)
    	candidates[dep]=curnum //恢复值
    	selected.pop()
    	
    	
    	return

    注意

    • 剪枝提升效率
    • 一般搜索的关键就是剪枝
    • 结果去重

    知识点

    • 集合选取
    • 剪枝

    复杂度

    • 空间复杂度O(n)
    • 时间复杂度O(2^n)
    • n为数组长度

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution {
    private:
        vector<vector<int>> res;
        void subSet(int dep, vector<int> &candidates, vector<int> &selected, int left) {
            if (0 == left) {
                res.push_back(selected);
                return;
            }
            if (left<0) return;
            if (dep >= candidates.size()) return;
            
            // 选取当前数字
            if (!(dep>0 && candidates[dep-1]==candidates[dep])) {
                int curnum = candidates[dep];
                candidates[dep] = -1;
                selected.push_back(curnum);
                subSet(dep + 1, candidates, selected, left - curnum);
                selected.pop_back();
                candidates[dep] = curnum;
            }
            
            // 不选取当前数字
            subSet(dep+1, candidates, selected, left);
        }
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            res.clear();
            vector<int> selected;
            sort(candidates.begin(), candidates.end());
            subSet(0, candidates, selected, target);
            return res;
        }
    };

    相关题目

    相关文章