分析

• 本题的考点：递归回溯。

• 不同于Leetcode 0039 组合总和，这一题candidates中可以有重复元素，并且candidates中的每个元素只能使用一次。

• 首先我们要对数组进行排序，这样方便我们统计每个数据出现的次数，比如某个数据出现2次，则最多选取这个数据2次。

• 类似于Leetcode 0039 组合总和的做法，直接暴搜即可，不过在循环某个数据可以放入几个时需要在循环中加入限制条件。

代码

• C++

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combinationSum2(vector<int>& c, int target) {

        sort(c.begin(), c.end());  // 方便后面统计数据出现次数

        dfs(c, target, 0);
        return ans;
    }

    void dfs(vector<int> &c, int target, int u) {

        if (target == 0) {
            ans.push_back(path);
            return;
        }
        if (u == c.size()) return;

        // 统计c[u]出现次数
        int k = u + 1;
        while (k < c.size() && c[k] == c[u]) k++;
        int cnt = k - u;

        for (int i = 0; c[u] * i <= target && i <= cnt; i++) {
            dfs(c, target - c[u] * i, k);
            path.push_back(c[u]);
        }

        for (int i = 0; c[u] * i <= target && i <= cnt; i++) path.pop_back();
    }
};

• Java

class Solution {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] c, int target) {

        Arrays.sort(c);

        LinkedList<Integer> path = new LinkedList<>();
        dfs(c, target, 0, path);
        return ans;
    }

    // 当前考察到c[u], 当前方案存储在path中
    private void dfs(int[] c, int target, int u, LinkedList<Integer> path) {
        // 每次递归path用的是同一个，因此需要恢复现场
        if (target == 0) {
            ans.add((List<Integer>) path.clone());
            return;
        }
        if (u == c.length) return;

        int k = u + 1;
        while (k < c.length && c[k] == c[u]) k++;
        int cnt = k - u;

        for (int i = 0; c[u] * i <= target && i <= cnt; i++) {  // 枚举放入c[u]的个数
            dfs(c, target - c[u] * i, k, path);
            path.add(c[u]);
        }
        for (int i = 0; c[u] * i <= target && i <= cnt; i++) path.removeLast();  // 恢复现场
    }
}

时空复杂度分析

• 时间复杂度：指数级别。

• 空间复杂度：和递归深度有关。