回溯算法练习——4、组合总和II(C++和Python描述)

2021/9/10 1:35:20

本文主要是介绍回溯算法练习——4、组合总和II(C++和Python描述),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

本题的力扣链接:https://leetcode-cn.com/problems/combination-sum-ii/

目录

  • 1、题目描述:
  • 2、思路:
  • 3、代码:
    • 3.1 python代码:
    • 3.2 C++代码:

1、题目描述:

在这里插入图片描述
在这里插入图片描述

2、思路:

在这里插入图片描述
在这里插入图片描述

其实看完上面的话,还是很迷,因此,这里再解释下:(来源)

这个避免重复当思想是在是太重要了。
这个方法最重要的作用是,可以让同一层级,不出现相同的元素。即
例1:
                  1
                 / \
                2   2  这种情况不会发生 但是却允许了不同层级之间的重复即:
               /     \
              5       5
例2:
                  1
                 /
                2      这种情况确是允许的
               /
              2  
                
为何会有这种神奇的效果呢?

首先 i-1 == i 是用于判定当前元素是否和之前元素相同的语句。这个语句就能砍掉例1。
可是问题来了,如果把所有当前与之前一个元素相同的都砍掉,那么例二的情况也会消失。 
因为当第二个2出现的时候,他就和前一个2相同了。
                
那么如何保留例2呢?
那么就用i > startIndex 来避免这种情况,你发现例1中的两个2是处在同一个层级上的,
例2的两个2是处在不同层级上的。
在一个for循环中,所有被遍历到的数都是属于一个层级的。我们要让一个层级中,
必须出现且只出现一个2,那么就放过第一个出现重复的2,但不放过后面出现的2。
第一个出现的2的特点就是 i == startIndex,第二个出现的2 特点是i > startIndex

3、代码:

3.1 python代码:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = [] # 保存从根到树叶路径上收集到元素的集合
        path = [] # 保存路径上符合条件的元素
        def backtracking(startIndex, s):
            if s == target:
                res.append(path.copy())
                return
            for i in range(startIndex, len(candidates)):
                if s + candidates[i] > target:
                    break
                if i > startIndex and candidates[i] == candidates[i-1]: # 这一步解题的关键,我上面专门有解释的
                    continue
                # 1.累计和,并收集路径上的元素
                s += candidates[i]
                path.append(candidates[i])
                # 2.递归,也就是下一层
                backtracking(i+1, s) # i+1表示当前元素不重复
                # 3.回溯,撤销操作
                s -= candidates[i]
                path.pop()
        candidates.sort() # 从小到大排序才能剪枝
        backtracking(0, 0)
        return res        

在这里插入图片描述

3.2 C++代码:

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int startIndex, int s){
        if(s == target){
            res.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size(); i++){
            if(s + candidates[i] > target){
                break;
            }
            // 下面这一步是这个题的精华,解释在前面
            if(i > startIndex && candidates[i-1] == candidates[i]){ // 这里数组不越界,是因为i是从startIndex开始遍历的
                continue;
            }
            // 1.累计和,并收集路径上的元素
            s += candidates[i];
            path.push_back(candidates[i]);
            // 2.递归,也就是下一层
            backtracking(candidates, target, i+1, s); // i+1表示当前元素不重复
            // 3.回溯,即撤销操作
            s -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); // 从小打到排序才能剪枝
        backtracking(candidates, target, 0, 0);
        return res;
    }
};

在这里插入图片描述



这篇关于回溯算法练习——4、组合总和II(C++和Python描述)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程