《代码随想录》LeetCode 刷题攻略

本文集文档发布于灏天文库

0040.组合总和II

文档摘要

参与本项目 ，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！ 这篇可以说是全网把组合问题如何去重，讲的最清晰的了！ 40.组合总和II 力扣题目链接 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

这篇可以说是全网把组合问题如何去重，讲的最清晰的了！

40.组合总和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]
]
​

算法公开课

《代码随想录》算法视频公开课：，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

这道题目和39.组合总和如下区别：

  1. 本题candidates 中的每个数字在每个组合中只能使用一次。
  2. 本题数组candidates的元素是有重复的，而39.组合总和是无重复元素的数组candidates

最后本题和39.组合总和要求一样，解集不能包含重复的组合。

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！

所以要在搜索的过程中就去掉重复组合。

很多同学在去重的问题上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂的先把题目过了。

这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）

强调一下，树层去重的话，需要对数组排序！

选择过程树形结构如图所示：

40.组合总和II

可以看到图中，每个节点相对于 39.组合总和我多加了used数组，这个used数组下面会重点介绍。

回溯三部曲

  • 递归函数参数

与39.组合总和套路相同，此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。

这个集合去重的重任就是used来完成的。

代码如下：

vector<vector<int>> result; // 存放组合集合
vector<int> path;           // 符合条件的组合
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
​
  • 递归终止条件

与39.组合总和相同，终止条件为 sum > target 和 sum == target。

代码如下：

if (sum > target) { // 这个条件其实可以省略
    return;
}
if (sum == target) {
    result.push_back(path);
    return;
}
​

sum > target 这个条件其实可以省略，因为在递归单层遍历的时候，会有剪枝的操作，下面会介绍到。

  • 单层搜索的逻辑

这里与39.组合总和最大的不同就是要去重了。

前面我们提到：要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过了呢。

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

这块比较抽象，如图：

40.组合总和II1

我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

  • used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  • used[i - 1] == false，说明同一树层candidates[i - 1]使用过

可能有的录友想，为什么 used[i - 1] == false 就是同一树层呢，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。

而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：

这块去重的逻辑很抽象，网上搜的题解基本没有能讲清楚的，如果大家之前思考过这个问题或者刷过这道题目，看到这里一定会感觉通透了很多！

那么单层搜索的逻辑代码如下：

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); // 和39.组合总和的区别1：这里是i+1，每个数字在每个组合中只能使用一次
    used[i] = false;
    sum -= candidates[i];
    path.pop_back();
}
​

注意sum + candidates[i] <= target为剪枝操作，在39.组合总和有讲解过！

回溯三部曲分析完了，整体C++代码如下：

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); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
            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;
    }
};

​
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

补充

这里直接用startIndex来去重也是可以的， 就不用used数组了。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // 要对同一树层使用过的元素进行跳过
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
            sum -= candidates[i];
            path.pop_back();
        }
    }

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

​

总结

本题同样是求组合总和，但就是因为其数组candidates有重复元素，而要求不能有重复的组合，所以相对于39.组合总和难度提升了不少。

关键是去重的逻辑，代码很简单，网上一搜一大把，但几乎没有能把这块代码含义讲明白的，基本都是给出代码，然后说这就是去重了，究竟怎么个去重法也是模棱两可。

所以Carl有必要把去重的这块彻彻底底的给大家讲清楚，就连“树层去重”和“树枝去重”都是我自创的词汇，希望对大家理解有帮助！

其他语言版本

Java

使用标记数组

class Solution {
  LinkedList<Integer> path = new LinkedList<>();
  List<List<Integer>> ans = new ArrayList<>();
  boolean[] used;
  int sum = 0;

  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    used = new boolean[candidates.length];
    // 加标志数组，用来辅助判断同层节点是否已经遍历
    Arrays.fill(used, false);
    // 为了将重复的数字都放到一起，所以先进行排序
    Arrays.sort(candidates);
    backTracking(candidates, target, 0);
    return ans;
  }

  private void backTracking(int[] candidates, int target, int startIndex) {
    if (sum == target) {
      ans.add(new ArrayList(path));
    }
    for (int i = startIndex; i < candidates.length; i++) {
      if (sum + candidates[i] > target) {
        break;
      }
      // 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
      if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
        continue;
      }
      used[i] = true;
      sum += candidates[i];
      path.add(candidates[i]);
      // 每个节点仅能选择一次，所以从下一位开始
      backTracking(candidates, target, i + 1);
      used[i] = false;
      sum -= candidates[i];
      path.removeLast();
    }
  }
}

​

不使用标记数组

class Solution {
  List<List<Integer>> res = new ArrayList<>();
  LinkedList<Integer> path = new LinkedList<>();
  int sum = 0;
  
  public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
    //为了将重复的数字都放到一起，所以先进行排序
    Arrays.sort( candidates );
    backTracking( candidates, target, 0 );
    return res;
  }
  
  private void backTracking( int[] candidates, int target, int start ) {
    if ( sum == target ) {
      res.add( new ArrayList<>( path ) );
      return;
    }
    for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {
      //正确剔除重复解的办法
      //跳过同一树层使用过的元素
      if ( i > start && candidates[i] == candidates[i - 1] ) {
        continue;
      }

      sum += candidates[i];
      path.add( candidates[i] );
      // i+1 代表当前组内元素只选取一次
      backTracking( candidates, target, i + 1 );

      int temp = path.getLast();
      sum -= temp;
      path.removeLast();
    }
  }
}
​

Python

回溯

class Solution:


    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target:
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)):
            if i > startIndex and candidates[i] == candidates[i - 1]:
                continue

            if total + candidates[i] > target:
                break

            total += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates, target, total, i + 1, path, result)
            total -= candidates[i]
            path.pop()

    def combinationSum2(self, candidates, target):
        result = []
        candidates.sort()
        self.backtracking(candidates, target, 0, 0, [], result)
        return result

​

回溯 使用used

class Solution:


    def backtracking(self, candidates, target, total, startIndex, used, path, result):
        if total == target:
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)):
            # 对于相同的数字，只选择第一个未被使用的数字，跳过其他相同数字
            if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]:
                continue

            if total + candidates[i] > target:
                break

            total += candidates[i]
            path.append(candidates[i])
            used[i] = True
            self.backtracking(candidates, target, total, i + 1, used, path, result)
            used[i] = False
            total -= candidates[i]
            path.pop()

    def combinationSum2(self, candidates, target):
        used = [False] * len(candidates)
        result = []
        candidates.sort()
        self.backtracking(candidates, target, 0, 0, used, [], result)
        return result

​

回溯优化

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

    def combinationSumHelper(self, candidates, target, index, path, results):
        if target == 0:
            results.append(path[:])
            return
        for i in range(index, len(candidates)):
            if i > index and candidates[i] == candidates[i - 1]:
                continue  
            if candidates[i] > target:
                break  
            path.append(candidates[i])
            self.combinationSumHelper(candidates, target - candidates[i], i + 1, path, results)
            path.pop()
​

Go

主要在于如何在回溯中去重

使用used数组

var (
    res [][]int
    path  []int
    used  []bool
)
func combinationSum2(candidates []int, target int) [][]int {
    res, path = make([][]int, 0), make([]int, 0, len(candidates))
    used = make([]bool, len(candidates))
    sort.Ints(candidates)   // 排序，为剪枝做准备
    dfs(candidates, 0, target)
    return res
}

func dfs(candidates []int, start int, target int) {
    if target == 0 {   // target 不断减小，如果为0说明达到了目标值
        tmp := make([]int, len(path))
        copy(tmp, path)
        res = append(res, tmp)
        return
    }
    for i := start; i < len(candidates); i++ {
        if candidates[i] > target {  // 剪枝，提前返回
            break
        }
        // 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
        }
        path = append(path, candidates[i])
        used[i] = true
        dfs(candidates, i+1, target - candidates[i])
        used[i] = false
        path = path[:len(path) - 1]
    }
}
​

不使用used数组

var (
    res [][]int
    path  []int
)
func combinationSum2(candidates []int, target int) [][]int {
    res, path = make([][]int, 0), make([]int, 0, len(candidates))
    sort.Ints(candidates)   // 排序，为剪枝做准备
    dfs(candidates, 0, target)
    return res
}

func dfs(candidates []int, start int, target int) {
    if target == 0 {   // target 不断减小，如果为0说明达到了目标值
        tmp := make([]int, len(path))
        copy(tmp, path)
        res = append(res, tmp)
        return
    }
    for i := start; i < len(candidates); i++ {
        if candidates[i] > target {  // 剪枝，提前返回
            break
        }
        // i != start 限制了这不对深度遍历到达的此值去重
        if i != start && candidates[i] == candidates[i-1] { // 去重
            continue
        }
        path = append(path, candidates[i])
        dfs(candidates, i+1, target - candidates[i])
        path = path[:len(path) - 1]
    }
}
​

JavaScript

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    const res = []; path = [], len = candidates.length;
    candidates.sort((a,b)=>a-b);
    backtracking(0, 0);
    return res;
    function backtracking(sum, i) {
        if (sum === target) {
            res.push(Array.from(path));
            return;
        }
        for(let j = i; j < len; j++) {
            const n = candidates[j];
            if(j > i && candidates[j] === candidates[j-1]){
              //若当前元素和前一个元素相等
              //则本次循环结束，防止出现重复组合
              continue;
            }
            //如果当前元素值大于目标值-总和的值
            //由于数组已排序，那么该元素之后的元素必定不满足条件
            //直接终止当前层的递归
            if(n > target - sum) break;
            path.push(n);
            sum += n;
            backtracking(sum, j + 1);
            path.pop();
            sum -= n;
        }
    }
};
​

使用used去重

var combinationSum2 = function(candidates, target) {
    let res = [];
    let path = [];
    let total = 0;
    const len = candidates.length;
    candidates.sort((a, b) => a - b);
    let used = new Array(len).fill(false);
    const backtracking = (startIndex) => {
        if (total === target) {
            res.push([...path]);
            return;
        }
        for(let i = startIndex; i < len && total < target; i++) {
            const cur = candidates[i];
            if (cur > target - total || (i > 0 && cur === candidates[i - 1] && !used[i - 1])) continue;
            path.push(cur);
            total += cur;
            used[i] = true;
            backtracking(i + 1);
            path.pop();
            total -= cur;
            used[i] = false;
        }
    }
    backtracking(0);
    return res;
};
​

TypeScript

function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);
    const resArr: number[][] = [];
    function backTracking(
        candidates: number[], target: number,
        curSum: number, startIndex: number, route: number[]
    ) {
        if (curSum > target) return;
        if (curSum === target) {
            resArr.push(route.slice());
            return;
        }
        for (let i = startIndex, length = candidates.length; i < length; i++) {
            if (i > startIndex && candidates[i] === candidates[i - 1]) {
                continue;
            }
            let tempVal: number = candidates[i];
            route.push(tempVal);
            backTracking(candidates, target, curSum + tempVal, i + 1, route);
            route.pop();

        }
    }
    backTracking(candidates, target, 0, 0, []);
    return resArr;
};
​

Rust

impl Solution {
    pub fn backtracking(result: &mut Vec<Vec<i32>>, path: &mut Vec<i32>, candidates: &Vec<i32>, target: i32, mut sum: i32, start_index: usize, used: &mut Vec<bool>) {
        if sum == target {
            result.push(path.to_vec());
            return;
        }
        for i in start_index..candidates.len() {
            if sum + candidates[i] <= target {
                if i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false { continue; }
                sum += candidates[i];
                path.push(candidates[i]);
                used[i] = true;
                Self::backtracking(result, path, candidates, target, sum, i + 1, used);
                used[i] = false;
                sum -= candidates[i];
                path.pop();
            }
        }
    }

    pub fn combination_sum2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        let mut path: Vec<i32> = Vec::new();
        let mut used: Vec<bool> = vec![false; candidates.len()];
        let mut candidates = candidates;
        candidates.sort();
        Self::backtracking(&mut result, &mut path, &candidates, target, 0, 0, &mut used);
        result
    }
}
​

C

int* path;
int pathTop;
int** ans;
int ansTop;
//记录ans中每一个一维数组的大小
int* length;
int cmp(const void* a1, const void* a2) {
    return *((int*)a1) - *((int*)a2);
}

void backTracking(int* candidates, int candidatesSize,  int target, int sum, int startIndex) {
    if(sum >= target) {
        //若sum等于target，复制当前path进入
        if(sum == target) {
            int* tempPath = (int*)malloc(sizeof(int) * pathTop);
            int j;
            for(j = 0; j < pathTop; j++) {
                tempPath[j] = path[j];
            }
            length[ansTop] = pathTop;
            ans[ansTop++] = tempPath;
        }
        return ;
    }

    int i;
    for(i = startIndex; i < candidatesSize; i++) {
        //对同一层树中使用过的元素跳过
        if(i > startIndex && candidates[i] == candidates[i-1])
            continue;
        path[pathTop++] = candidates[i];
        sum += candidates[i];
        backTracking(candidates, candidatesSize, target, sum, i + 1);
        //回溯
        sum -= candidates[i];
        pathTop--;
    }
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    path = (int*)malloc(sizeof(int) * 50);
    ans = (int**)malloc(sizeof(int*) * 100);
    length = (int*)malloc(sizeof(int) * 100);
    pathTop = ansTop = 0;
    //快速排序candidates，让相同元素挨到一起
    qsort(candidates, candidatesSize, sizeof(int), cmp);

    backTracking(candidates, candidatesSize, target, 0, 0);

    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = length[i];
    }
    return ans;
}
​

Swift

func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
    // 为了方便去重复，先对集合排序
    let candidates = candidates.sorted()
    var result = [[Int]]()
    var path = [Int]()
    func backtracking(sum: Int, startIndex: Int) {
        // 终止条件
        if sum == target {
            result.append(path)
            return
        }

        let end = candidates.count
        guard startIndex < end else { return }
        for i in startIndex ..< end {
            if i > startIndex, candidates[i] == candidates[i - 1] { continue } // 去重复
            let sum = sum + candidates[i] // 使用局部变量隐藏回溯
            if sum > target { continue } // 剪枝

            path.append(candidates[i]) // 处理
            backtracking(sum: sum, startIndex: i + 1) // i+1避免重复访问
            path.removeLast() // 回溯
        }
    }
    backtracking(sum: 0, startIndex: 0)
    return result
}
​

Scala

object Solution {
  import scala.collection.mutable    
  def combinationSum2(candidates: Array[Int], target: Int): List[List[Int]] = {
    var res = mutable.ListBuffer[List[Int]]()
    var path = mutable.ListBuffer[Int]()
    var candidate = candidates.sorted

    def backtracking(sum: Int, startIndex: Int): Unit = {
      if (sum == target) {
        res.append(path.toList)
        return
      }

      for (i <- startIndex until candidate.size if sum + candidate(i) <= target) {
        if (!(i > startIndex && candidate(i) == candidate(i - 1))) {
          path.append(candidate(i))
          backtracking(sum + candidate(i), i + 1)
          path = path.take(path.size - 1)
        }
      }
    }

    backtracking(0, 0)
    res.toList
  }
}
​

C#

public class Solution
{
    public List<IList<int>> res = new List<IList<int>>();
    public List<int> path = new List<int>();
    public IList<IList<int>> CombinationSum2(int[] candidates, int target)
    {

        Array.Sort(candidates);
        BackTracking(candidates, target, 0, 0);
        return res;
    }
    public void BackTracking(int[] candidates, int target, int start, int sum)
    {
        if (sum > target) return;
        if (sum == target)
        {
            res.Add(new List<int>(path));
            return;
        }
        for (int i = start; i < candidates.Length && sum + candidates[i] <= target; i++)
        {
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            sum += candidates[i];
            path.Add(candidates[i]);
            BackTracking(candidates, target, i + 1, sum);
            sum -= candidates[i];
            path.RemoveAt(path.Count - 1);
        }
    }
}
​

发布者: 作者: 转发
评论区 (0)
U
0/500