【Day 81 】2022-06-20 - 40 组合总数 II

[azl397985856]

40 组合总数 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/combination-sum-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] ]

[xil324]

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort();
        res = [];
        self.findTarget(candidates, target, 0, [], res); 
        return res;

    def findTarget(self, candidates, target, start, temp, res):
        if sum(temp) == target:
            res.append(temp[:]);
            return;

        if sum(temp) > target:
            return;

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i-1]: #剪枝
                continue;
            temp.append(candidates[i]);
            self.findTarget(candidates, target, i+1, temp,res);
            temp.pop();

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

[MichaelXi3]

Idea

回溯 + 剪枝

Code

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // Sort to avoid repetitive res
        Arrays.sort(candidates);

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        backTrack(candidates, target, list, 0, res);
        return res;
    }

    private void backTrack(int[] candidates, int cur, List<Integer> list, int pos, List<List<Integer>> res) {
        // Base cases
        if (cur < 0) { return;} // Not match
        if (cur == 0) { res.add(new ArrayList<>(list));} // Match the target

        for (int i = pos; i < candidates.length; i++) {
            // ❗️Avoid the repetitive candidates cause repetitive res
            if (i > pos && candidates[i] == candidates[i-1]) { continue;}

            list.add(candidates[i]);
            backTrack(candidates, cur - candidates[i], list, i+1, res);
            list.remove(list.size() - 1);
        }
    }
}

[houmk1212]

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, target, path, 0, 0);
        return res;
    }

    public void dfs(int[] condidates, int target, List<Integer> path, int sum, int k) {
        if (target == sum) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = k; i < condidates.length; i++) {
            if (sum + condidates[i] <= target) {
                if (i > k && condidates[i] == condidates[i-1]){
                    continue;
                }
                path.add(condidates[i]);
                dfs(condidates, target, path, sum + condidates[i], i+1);
                path.remove(path.size() - 1);
            }
        }
    }
}

[MoonLee001]

var combinationSum2 = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const n = candidates.length;
    const vis = new Array(n).fill(false);
    let res = [];
    const backtrack = (start, path, sum) => {
        if (sum == 0) {
            res.push(path.slice());
            return;
        }

        if (sum < 0) {
            return;
        }

        for (let i = start; i < n; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && !vis[i - 1]) {
                continue;
            }
            vis[i] = true;
            path.push(candidates[i]);
            sum -= candidates[i];
            backtrack(i + 1, path, sum);
            vis[i] = false;
            path.pop();
            sum += candidates[i];
        }
    }
    backtrack(0, [], target);
    return res;
};

[freedom0123]

class Solution {
    List<List<Integer>> resource = new ArrayList();
    LinkedList<Integer> path = new LinkedList();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,0, target,0);
        return resource;
    }
    public void dfs(int []arr,int index,int target,int NowSum){
        if(NowSum==target){
            resource.add(new ArrayList<>(path));
            return;
        }
        for(int i = index ;i<arr.length && NowSum+arr[i]<=target;i++){
            if (i > index && arr[i] == arr[i - 1]) {
                continue;
            }
            NowSum+=arr[i];
            path.add(arr[i]);
            dfs(arr,i+1,target,NowSum);
            path.removeLast();
            NowSum-=arr[i];
        }
    }
}

[ShawYuan97]

思路

• 回溯法

• 最后结果，做到不重不漏，而且每个数字只能使用一次

  关键点

• 对candidates进行排序，每个元素只能使用一次，而且left_num<0可以提前退出

• 对于相同的元素，那么可以跳过当前循环

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        """
        从candidates中选择数字，使其和为target（每个数字在每个组合中只能使用一次）

        提示：回溯+剪枝
        """
        size = len(candidates)
        if size == 0:
            return []

        candidates.sort()

        path,res = [],[]
        self.find_path(candidates,path,res,target,0,size)
        return res 

    def find_path(self,candidates,path,res,target,begin,size):
        if target == 0:
            res.append(path.copy())
        else:
            for i in range(begin,size):
                left_num = target - candidates[i]
                # 由于candidates是升序的，如果当前元素都超过了left_num,后面的元素可以直接舍弃
                if left_num < 0 :
                    break
                # 如果存在重复元素，前一个元素已经遍历了后一个元素与之后元素组合的所有可能
                if i > begin and candidates[i] == candidates[i-1]:
                    continue
                path.append(candidates[i])
                self.find_path(candidates,path,res,left_num,i+1,size)
                path.pop()

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$

[taojin1992]

/*
# Evaluate:

n = candidates.length
candidate_min is the min candidate value

Prime ' below means duplicates excluded, bounded by the current size to choose from

n' branches
(n-1)' branches    => stack depth/tree height = target/(candidate_min)
(n-2)' branches 
...

after sorting, time complexity = 

n * (n - 1) * ... (n - (target/candidate_min - 1)) * copy&paste curList

= [n! / (n - target/candidate_min)!] * (target/candidate_min)

## Time:
O(nlogn) + [n! / (n - target/candidate_min)!] * (target/candidate_min)

## Space:
stack depth + curList max length + [output]

O(target/min_candidate) + O(target/min_candidate) [+ O(n * (n - 1) * ... (n - (target/candidate_min - 1)))]

*/

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, target, 0, result, new ArrayList<>());
        return result;
    }

    private void dfs(int[] candidates, int target, int curIndex, List<List<Integer>> result, List<Integer> curList) {
        if (target < 0) return;
        if (target == 0) {
            result.add(new ArrayList<>(curList));
            return;
        }
        for (int i = curIndex; i < candidates.length && candidates[i] <= target; i++) {

            if (i > curIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            curList.add(candidates[i]);
            dfs(candidates, target - candidates[i], i + 1, result, curList);
            curList.remove(curList.size() - 1);
        }
    }
}

[miss1]

思路

回溯，关键在于怎么去重

先对candidates排序。当遍历完一个数的所有情况(result长度为0时)，开始遍历下一个数时，判断这个数是否跟前一个数相等，若相等，则重复了，跳过。得到一个结果时，result pop出来的值n，跳过后面所有等于n的数，再继续循环回溯。

代码

var combinationSum2 = function(candidates, target) {
  candidates.sort((a, b) => a - b);
  let res = [];
  const backTrack = function(result, sum, start) {
    if (sum > target) return;
    if (sum === target) {
      res.push([...result]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      // 跳过重复的数
      if (result.length === 0 && i > 0 && candidates[i] === candidates[i - 1]) continue;
      result.push(candidates[i]);
      sum += candidates[i];
      backTrack(result, sum, i + 1);
      let n = result.pop();
      sum -= n;
      // 跳过重复的数
      while (i < candidates.length - 1 && candidates[i + 1] === candidates[i]) i++;
    }
  };
  backTrack([], 0, 0);
  return res;
};

复杂度

• time: O(n) n为结果总长度
• space: O(target)

[maggiexie00]

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    ans=[]
    def dfs(target,start,tmp):            
        for i in range(start,len(candidates)):
            if i>start and candidates[i]==candidates[i-1]:
                    continue
            rest=target-candidates[i]
            if rest<0:
                break
            elif rest==0:
                ans.append(tmp+[candidates[i]])
                return

            dfs(rest,i+1,tmp+[candidates[i]])

    dfs(target,0,[])
    return ans

[currybeefer]

vector<vector<int>> res;
vector<int> track;
int trackSum;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
{
    if(candidates.size()==0) return res;
    sort(candidates.begin(),candidates.end());
    BackTrack(candidates,0,target);
    return res;
}
void BackTrack(vector<int>& nums,int start,int target)
{
    if(trackSum==target)
    {
        res.push_back(track);
        return;
    }
    if(trackSum>target) return;
    for(int i=start;i<nums.size();i++)
    {
        if(i>start && nums[i]==nums[i-1]) continue;

        track.push_back(nums[i]);
        trackSum+=nums[i];

        BackTrack(nums,i+1,target);

        track.pop_back();
        trackSum-=nums[i];
    }

}

[Jongeehsu]

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; import java.util.List;

public class Solution {

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    int len = candidates.length;
    List<List<Integer>> res = new ArrayList<>();
    if (len == 0) {
        return res;
    }

    // 关键步骤
    Arrays.sort(candidates);

    Deque<Integer> path = new ArrayDeque<>(len);
    dfs(candidates, len, 0, target, path, res);
    return res;
}

/**
 * @param candidates 候选数组
 * @param len        冗余变量
 * @param begin      从候选数组的 begin 位置开始搜索
 * @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
 * @param path       从根结点到叶子结点的路径
 * @param res
 */
private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
    if (target == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = begin; i < len; i++) {
        // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
        if (target - candidates[i] < 0) {
            break;
        }

        // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
        if (i > begin && candidates[i] == candidates[i - 1]) {
            continue;
        }

        path.addLast(candidates[i]);
        // 调试语句 ①
        // System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));

        // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
        dfs(candidates, len, i + 1, target - candidates[i], path, res);

        path.removeLast();
        // 调试语句 ②
        // System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
    }
}

public static void main(String[] args) {
    int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
    int target = 8;
    Solution solution = new Solution();
    List<List<Integer>> res = solution.combinationSum2(candidates, target);
    System.out.println("输出 => " + res);
}

}

[Ellie-Wu05]

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

    def backtrack(comb, remain, curr, results):

        if remain == 0:
            # make a deep copy of the resulted combination
            results.append(list(comb))
            return

        for next_curr in range(curr, len(candidates)):

            if next_curr > curr and candidates[next_curr] == candidates[next_curr-1]:
                continue

            pick = candidates[next_curr]
            # optimization: skip the rest of elements starting from 'curr' index
            if remain - pick < 0:
                break

            comb.append(pick)
            backtrack(comb, remain - pick, next_curr + 1, results)
            comb.pop()

    candidates.sort()

    comb, results = [], []
    backtrack(comb, target, 0, results)

    return results

[xingchen77]

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        visited = set()
        res = []
        candidates.sort()

        def dfs(idx, cur, path):
            if cur == 0:
                res.append(path[:])
                return 
            if idx == n:
                return 

            if idx > 0 and candidates[idx] == candidates[idx - 1] and (idx -1) not in visited:
                dfs(idx + 1, cur, path)
                return 

            if candidates[idx] <= cur:
                path.append(candidates[idx])
                visited.add(idx)
                dfs(idx + 1, cur - candidates[idx], path)
                visited.remove(idx)
                path.pop()
            dfs(idx + 1, cur, path)
        dfs(0, target, [])
        return res

[Geek-LX]

6.20

思路：剪枝、数组、回溯

代码：

class Solution:
    def combinationSum2(self, candidates, target):
        lenCan = len(candidates)
        if lenCan == 0:
            return []
        candidates.sort()
        path = []
        res = []
        self.backtrack(candidates, target, lenCan, 0, 0, path, res)
        return res

    def backtrack(self, curCandidates, target, lenCan, curSum, indBegin, path, res):
            # 终止条件
            if curSum == target:
                res.append(path.copy())
            for index in range(indBegin, lenCan):
                nextSum = curSum + curCandidates[index]
                # 减枝操作
                if nextSum > target:
                    break
                # 通过减枝避免重复解的出现
                if index > indBegin and curCandidates[index-1] == curCandidates[index]:
                    continue
                path.append(curCandidates[index])
                # 由于元素只能用一次，所以indBegin = index+1
                self.backtrack(curCandidates, target, lenCan, nextSum, index+1, path, res)
                path.pop()

复杂度分析

空间复杂度：O(target/min)

时间复杂度： O(N*2^N)

[wychmod]

思路

精细化剪枝

代码

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        print(candidates)
        def process(ans, cur_list, index, cur):
            if cur < 0:
                return
            if cur == 0:
                ans.append(cur_list.copy())
            for i in range(index, len(candidates)):
                if i > index and candidates[i] == candidates[i-1]:
                    continue
                cur_list.append(candidates[i])
                print(cur_list)
                process(ans, cur_list, i+1, cur-candidates[i])
                cur_list.pop()
        ans = []
        process(ans, [], 0, target)
        return ans

[Shuchunyu]

class Solution { List<int[]> freq = new ArrayList<int[]>(); List<List> ans = new ArrayList<List>(); List sequence = new ArrayList();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    for (int num : candidates) {
        int size = freq.size();
        if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
            freq.add(new int[]{num, 1});
        } else {
            ++freq.get(size - 1)[1];
        }
    }
    dfs(0, target);
    return ans;
}

public void dfs(int pos, int rest) {
    if (rest == 0) {
        ans.add(new ArrayList<Integer>(sequence));
        return;
    }
    if (pos == freq.size() || rest < freq.get(pos)[0]) {
        return;
    }

    dfs(pos + 1, rest);

    int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
    for (int i = 1; i <= most; ++i) {
        sequence.add(freq.get(pos)[0]);
        dfs(pos + 1, rest - i * freq.get(pos)[0]);
    }
    for (int i = 1; i <= most; ++i) {
        sequence.remove(sequence.size() - 1);
    }
}

}

[carterrr]

class Solution { List<List> res = new ArrayList<>(); List tmp = new ArrayList<>(); public List<List> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); bt(candidates, target, 0); return res; }

private void bt(int[] candidates, int remain, int fromIdx) {
    if(remain == 0) {
        res.add(new ArrayList<>(tmp)); return;
    }

    if(remain < 0 || fromIdx  >= candidates.length) return;
    for(int i = fromIdx; i < candidates.length; i++) {
        // 关键  循环内部剪枝  重复的组合不能再次出现 应该被剪掉
        if(i > fromIdx && candidates[i] == candidates[i - 1]) continue; // 第一层进来 i == fromIdx 可以使用重复但不同位的数字， 其他层不允许  因为前面取过了
        tmp.add(candidates[i]);
        bt(candidates, remain - candidates[i], i + 1);
        tmp.remove(tmp.size() - 1);
    }
}

}

[bzlff]

public List<List> combinationSum(int[] candidates, int target) {

List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new LinkedList<>();
helper(res, list, candidates, target, 0);
return res;

}

public void helper(List<List> res, List list, int[] candidates, int cur, int pos) {

if (cur < 0)
    return;

if (cur == 0) {

    res.add(new LinkedList<>(list));
    return;
}

for (int i = pos; i < candidates.length; i++) {

    list.add(candidates[i]);
// 变化在下面这行呢
    helper(res, list, candidates, cur - candidates[i], i + 1);
    list.remove(list.size() - 1);
}

}

[LQyt2012]

思路

回溯

代码

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.result = []
        path = []
        candidates.sort()
        self.backtrace(candidates, 0, path, target)
        return self.result

    def backtrace(self, candidates, begin, path, target):
        if sum(path) > target:
            return

        if sum(path) == target:
            self.result.append(path[:])
            return

        for i in range(begin, len(candidates)):
            if i > begin and candidates[i] == candidates[i-1]:
                continue
            path.append(candidates[i])
            print(path)
            self.backtrace(candidates, i+1, path, target)
            path.remove(candidates[i])
        return

import "sort"

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    result := &[][]int{}
    path := []int{}
    backTrace(candidates, path, 0, target, result)
    return *result
}

func backTrace(candidates []int, path []int, begin, target int, result *[][]int) {
    if sum(path) > target {
        return
    }
    if sum(path) == target {
        res := make([]int, len(path))
        copy(res, path)
        *result = append(*result, res)
        return
    }

    for i:=begin;i<len(candidates);i++ {
        if i>begin && candidates[i] == candidates[i-1] {
            continue
        }
        path = append(path, candidates[i])
        backTrace(candidates, path, i+1, target, result)
        path = path[:len(path)-1]
    }
    return
}

func sum(nums []int) int {
    sum := 0
    for i := range nums {
        sum += nums[i]
    }
    return sum
}

复杂度分析

时间复杂度：O(2^N*N)
空间复杂度：O(target)

[zhishinaigai]

class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> sequence;

public:
    void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.push_back(sequence);
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) {
            return;
        }

        dfs(pos + 1, rest);

        int most = min(rest / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= most; ++i) {
            sequence.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (int num: candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1);
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ans;
    }
};

[zhishinaigai]

class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> sequence;

public:
    void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.push_back(sequence);
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) {
            return;
        }

        dfs(pos + 1, rest);

        int most = min(rest / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= most; ++i) {
            sequence.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (int num: candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1);
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ans;
    }
};

[xiayuhui231]

题目

组合总和

代码

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // used[i - 1] == true，说明同一树支candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used);
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }
};

[eugeneyuan]

思路

剪枝优化

代码

class Solution:

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(begin, length, residual, path):
            if residual < 0:
                return 

            if residual == 0:
                res.append(path[:])
                return 

            for i in range(begin, length):
                if candidates[i] > residual:
                    break

                if i > begin and candidates[i - 1] == candidates[i]:
                    continue

                path.append(candidates[i])
                dfs(i + 1, length, residual - candidates[i], path)
                path.pop()

        length = len(candidates)
        if length == 0:
            return []

        res = []
        candidates.sort()
        dfs(0, length, target, [])
        return res

[flyzenr]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        def backtrack(candidates,target,sum,startIndex):
            if sum == target: res.append(path[:])
            for i in range(startIndex,len(candidates)):  #要对同一树层使用过的元素进行跳过
                if sum + candidates[i] > target: return 
                if i > startIndex and candidates[i] == candidates[i-1]: continue  #直接用startIndex来去重,要对同一树层使用过的元素进行跳过
                sum += candidates[i]
                path.append(candidates[i])
                backtrack(candidates,target,sum,i+1)  #i+1:每个数字在每个组合中只能使用一次
                sum -= candidates[i]  #回溯
                path.pop()  #回溯
        candidates = sorted(candidates)  #首先把给candidates排序，让其相同的元素都挨在一起。
        backtrack(candidates,target,0,0)
        return res

[JiangWenqi]

class Solution {
 private:
  vector<vector<int>> res;
  vector<int> path;
  void dfs(int start, vector<int>& candidates, int target) {
    if (target == 0) {
      res.push_back(path);
      return;
    }
    if (start == candidates.size()) return;

    int end = start + 1;
    while (end < candidates.size() && candidates[start] == candidates[end])
      end++;
    int cnt = end - start;
    for (int i = 0; candidates[start] * i <= target && i <= cnt; i++) {
      dfs(end, candidates, target - candidates[start] * i);
      path.push_back(candidates[start]);
    }
    for (int i = 0; candidates[start] * i <= target && i <= cnt; i++) {
      path.pop_back();
    }
  }

 public:
  vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    dfs(0, candidates, target);
    return res;
  }
};

[JiangWenqi]

class Solution {
 private:
  vector<vector<int>> res;
  vector<int> path;
  void dfs(int start, vector<int>& candidates, int target) {
    if (target == 0) {
      res.push_back(path);

    } else if (target > 0) {
      for (int i = start; i < candidates.size(); i++) {
        if (i > start && candidates[i] == candidates[i - 1]) continue;
        path.push_back(candidates[i]);
        dfs(i + 1, candidates, target - candidates[i]);
        path.pop_back();
      }
    }
  }

 public:
  vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    dfs(0, candidates, target);
    return res;
  }
};

[Yongxi-Zhou]

思路

backtracking, 在每轮forloop遇到有重复的就跳过

代码

    class Solution:
        def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
            res = []
            candidates.sort()
            self.backtracking(candidates, target, res, [], 0)
            return res

        def backtracking(self, nums, target, res, temp, idx):
            if target == 0:
                res.append(temp[:])
                return
            elif target < 0:
                return

            for i in range(idx, len(nums)):
                if i > idx and nums[i] == nums[i - 1]:
                    continue
                temp.append(nums[i])
                self.backtracking(nums, target - nums[i], res, temp, i + 1)
                temp.pop()

复杂度

time O(N^T) space O(T)

[XXjo]

var combinationSum2 = function(candidates, target) {
    let res = [];
    let path = [];
    candidates = candidates.sort((a, b) => a - b);  //排序是为了方便后面去掉由于candidates存在重复的数字导致结果重复的问题
    var backtrack = function(candidates, target, path, startIndex, length){
        if(target < 0) return;
        if(target === 0){
            res.push([...path]);
            return;
        }
        for(let i = startIndex; i < length; i++){
            if((candidates[i] === candidates[i - 1]) && (i > startIndex)){  //由于candidates已经排序，所以可以通过这种方式去掉重复
                continue;
            }
            path.push(candidates[i]);
            backtrack(candidates, target - candidates[i], path, i + 1, length);
            path.pop();
        }
    }

    backtrack(candidates, target, path, 0, candidates.length);
    return res;
};

[revisegoal]

回溯

class Solution {
    int skip = -1;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(ans, new ArrayList<Integer>(), candidates, target, 0);
        return ans;
    }

    void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start) {
        if (remain < 0) {
            return;
        }
        if (remain == 0) {
            List<Integer> addition = new ArrayList<>(tempList);
            list.add(addition);
        }

        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

• time: O(n * 2^n)
• space: O(n)

[VictorHuang99]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
 var combinationSum2 = function (candidates, target) {
     let res = []
     let track = []
     const backtrack = (start, sum) => {
         if (sum === target) {
             return res.push(track.slice())
         }
         if (sum > target) {
             return
         }
         for (let i = start; i < candidates.length; i++) {
             if (i-1 >= start && candidates[i-1] == candidates[i]) {
                 continue
             }
            //  选择
             track.push(candidates[i])
             sum += candidates[i]
            //  递归
             backtrack(i+1, sum)
            //  撤销选择
            track.pop()
            sum -= candidates[i]
         }
     }
     candidates.sort((a,b) => a-b)
     backtrack(0, 0)
     return res
 }

[tensorstart]

var combinationSum2 = function(candidates, target) {
    let n = candidates.length;
    let res = [];
    let tmpPath = [];
    candidates = candidates.sort((a,b) => {return a - b})
    let backtrack = (tmpPath,target,start) => {
        if(target == 0){
            res.push(tmpPath);
            return;
        }
        for(let i = start;i < n;i++){
            if(target < candidates[i]) break;
            if(i > start && candidates[i-1] == candidates[i]) continue;
            tmpPath.push(candidates[i]);
            backtrack(tmpPath.slice(),target - candidates[i],i + 1);
            tmpPath.pop();
        }
    }
    backtrack(tmpPath,target,0);
    return res;
};