1 题目

题目：数字组合II（Combination Sum II）
描述：给定一个数组 num 和一个整数 target。 找到 num 中所有的数字之和为 target 的组合。

1. 在同一个组合中, num 中的每一个数字仅能被使用一次。
2. 所有数值 (包括 target ) 都是正整数。
3. 返回的每一个组合内的数字必须是非降序的。
4. 返回的所有组合之间可以是任意顺序。
5. 解集不能包含重复的组合。

lintcode题号——153，难度——medium

样例1：

输入: num = [7,1,2,5,1,6,10], target = 8
输出: [[1,1,6],[1,2,5],[1,7],[2,6]]

样例2：

输入: num = [1,1,1], target = 2
输出: [[1,1]]
解释: 解集不能包含重复的组合

2 解决方案

2.1 思路

  与数字组合的第一题¹相比，多了一个条件，每个数字只能使用一次。该题无法提前在原序列中去重，需要在递归过程中完成去重，目标是在同一层级去除重复的分支。

2.2 图解

num = [1,1,2,2,3], target = 5的情况下，深度优先搜索的图如下：

2.3 时间复杂度

  深度优先搜索的时间复杂度是逻辑图上的节点数（即所有元素的组合数，n个元素，每个元素都有取或不取两种可能，所以是2的n次方）与处理每个节点的耗时（for循环n次）的乘积，该题的算法的时间复杂度为O(2^n * n)。

深度优先搜索的时间复杂度计算没有通用的方式，只能根据具体题目计算，可以理解成看作答案个数与构造每个答案花费的时间的乘积。

2.4 空间复杂度

  使用了vector数据结构保存节点，算法的空间复杂度为O(n)。

3 源码

细节：

1. 与前一题不同的是，dfs中的序号i每次加一，取下一个数。
2. 去重的方式需要使用同一层级的去重方式，即i != startindex，而不能简单使用i != 0。
3. 去重的方式也可以使用set，使用set去重不要求原序列有序，更加通用，同一层级去重不需要回溯。

• i与startIndex比较，它判断每层的非首元素和原序列前一个元素是否相同，首先是防止i-1越界，它能够防止同一层级中出现相同的元素，但不会禁止各个分支的第一个分叉（即i=startIndex）中出现与原序列前一个元素重复的元素。即示例中的竖分支中可以存在相同元素，而同一层级的相同元素则会被去重。

C++版本：

/**
* @param num: Given the candidate numbers
* @param target: Given the target number
* @return: All the combinations that sum to target
*/
vector<vector<int>> combinationSum2(vector<int> &num, int target) {
    // write your code here
    vector<vector<int>> results;
    if (num.empty())
    {
        return results;
    }

    sort(num.begin(), num.end());
    
    vector<int> path;
    dfs(num, path, 0, target, results);
    return results;
}

void dfs(vector<int> & num, vector<int> path, int startIndex, int remainTarget, vector<vector<int>> & results)
{
    if (remainTarget == 0)
    {
        results.push_back(path);
        return;
    }

    //set<int> duplicate;
    for (int i = startIndex; i < num.size(); i++)
    {
        // 用于在同一个层级之间去重，不考虑每层的第一个元素即i=startIndex
        if (i != startIndex && num.at(i) == num.at(i - 1))
        {
            continue;
        }

        //if (duplicate.find(num.at(i)) != duplicate.end())
        //{
        //    continue;
        //}

        // 结果超过目标值，则停止，防止后续的无效搜索
        if (remainTarget < num.at(i))
        {
            break;
        }

        path.push_back(num.at(i));
        // 题中不能重复取同一个值，所以递归依然从i + 1开始，而不是i
        dfs(num, path, i + 1, remainTarget - num.at(i), results);
        path.pop_back();
    }
}

---

1. 数字组合：https://blog.csdn.net/SeeDoubleU/article/details/124418403 ↩︎