fucking-algorithm

fucking-algorithm copied to clipboard

文章链接点这里：回溯算法秒杀所有排列/组合/子集问题

评论礼仪 见这里，违者直接拉黑。

强

顶礼膜拜，太牛逼了！

太绝了！

感谢大佬的文章。大佬的文章最强的地方在于，通过归纳总结框架，高度抽象出来了一类问题。比如要不要重复选，其实就取决于下一次递归是i还是i+1。很好。

关于全排列去重，个人觉得有一个更好理解的方案。按照回溯框架的思想，每次递归的时候遍历可选列表。什么时候会造成答案重复呢？在同一个位置上，同样值的元素被选了多次。比如[2, 2]，如果选了第一个2，下次还选2，就会造成重复。为了避免这个重复，可以在遍历的时候判断一下现在要选的元素是否和上一次选择过的相等。相等就跳过。伪代码如下：

for (int i = 0, last = -1; i < nums.length; ++i) {
    if (last > -1 && nums[i] == nums[last]) continue;
    if (visited[i])   continue;
    // make choice
    last = i;
    visited[i] = true;
    path.add(nums[i]);
    
    // recursive call
    recur(path, nums);
    
    // cancel choice
    visited[i] = false;
    path.removeLast();
}

不错

@BIT-zhaoyang 这个思路也不错！我的代码：

void backtrack(int[] nums, LinkedList<Integer> track) {
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    // 记录之前树枝上元素的值
    // 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
    int prevNum = -666;
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (used[i]) {
            continue;
        }
        if (nums[i] == prevNum) {
            continue;
        }

        track.add(nums[i]);
        used[i] = true;
        // 记录这条树枝上的值
        prevNum = nums[i];

        backtrack(nums, track);

        track.removeLast();
        used[i] = false;
    }
}

第 40 题「 组合总和 II」的backtrack在 往track里添加元素的代码是不是写错了， 应该是 track.add(nums[i]); 而不是 track.add([i]); ?

@TimurJiangShan 是写错了，已修复，感谢指正

讲的很好，点个赞！另外有两个格式的小问题，

• 1. 排队（元素可查不可复选）解法代码中，backtrack 函数调用参数数量不一致

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
boolean[] used;

public List<List<Integer>> permuteUnique(int[] nums) {
    ...
    // 调用是传了两个参数
    backtrack(nums, track);
    ...
}
// 只有一个参数
void backtrack(int[] nums) {
      .....
}

• 2. 读者解法中，new 前后多了加粗标记 *

void backtrack(int[] nums, LinkedList<Integer> track) {
    if (track.size() == nums.length) {
        // 这里多了*
        res.add(**new** LinkedList(track));
        return;
    }
    ....
}

@zhyozhi 感谢指正，已修复~

第39题的回溯部分应该是i而不是i +1吧？不然没法重复选择啊。一点拙见，如果不对的话希望能指正一下，谢谢大神！

class Solution:

    def __init__(self):
        self.res = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        track = []
        self.backtrack(candidates, target, 0, track, 0)
        return self.res

    def backtrack(self, candidates, target, start, track, trackSum):
        if trackSum == target:
            self.res.append(copy.deepcopy(track))
            return
        elif trackSum > target:
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            track.append(candidates[i])
            trackSum += candidates[i]
            self.backtrack(candidates, target, i, track, trackSum)
            track.pop()
            trackSum -= candidates[i]

@yuhaoban 你看错了吧，我写的就是 i 不是 i + 1 啊？

216题 组合总和3 有兴趣的朋友可以继续改进，此处实在想不到如何删除个数不符合 k要求的组合，所以直接在外部对result动手脚，最后虽然是 1ms 还是只能击败 14%的人 哈哈，

class Solution {
    List<List<Integer>> result = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTrack(n,k,0,1);
        Iterator<List<Integer>> iterator = result.iterator();
        while(iterator.hasNext()){
            if(iterator.next().size() != k){
                iterator.remove();
            }
        }
        return result;
    }
    private void backTrack(int target,int k,int sum,int start){
        if(sum == target){
            result.add(new LinkedList<>(track));
            return;
        }
        if(sum > target){
            return;
        }
        for(int i = start; i<= 9; i++){
            sum += i;
            k--;
            track.add(i);
            backTrack(target,k,sum,i+1);
            track.removeLast();
            k++;
            sum -= i;
        }
    }
}

发现对于排列（元素可重不可复选）的剪枝部分，使用 if(i > 0 && nums[i] == nums[i - 1] && used[i-1])也可以通过测试，具体解释为 如果前面的相邻相等元素被用过，则跳过。 貌似更好理解些。:)

用过，则跳过。 貌似更好理解些

即使used[i -1] = true（添加了nums[i - 1]），也是有可能需要选择nums[i]的。

&& used[i-1])直接忽略了上述的可能性，结果可能出错

@sxcnmslll @FZ20192019 其实你们的说法都不太准确，我把对 used[i-1] 的分析补充在文中了，可以看下

2022.4.5 mark

对于某些重复元素的题 我可不可以先去重再按无重复不可复选的思路来做😂

讲的很细致啊，明天再复习一下

好文赞一个。@zhongweiLeex，按照模板的写法这道216可以写成这样

class Solution {
vector<vector<int>> res;
vector<int> track;
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtrack(n, k, 1, 0);
        return res;
    }
    void backtrack(int n, int k, int start, int curSum){
        if(track.size() == k && curSum == n){
            res.push_back(track);
            return;
        }
        if(curSum > n){
            return;
        }
        for(int i=start; i<=9; i++){
            track.push_back(i);
            curSum += i;
            backtrack(n, k, i+1, curSum);
            track.pop_back();
            curSum -= i;
        }
    }
};

好文赞一个。@zhongweiLeex，按照模板的写法这道216可以写成这样

class Solution {
vector<vector<int>> res;
vector<int> track;
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtrack(n, k, 1, 0);
        return res;
    }
    void backtrack(int n, int k, int start, int curSum){
        if(track.size() == k && curSum == n){
            res.push_back(track);
            return;
        }
        if(curSum > n){
            return;
        }
        for(int i=start; i<=9; i++){
            track.push_back(i);
            curSum += i;
            backtrack(n, k, i+1, curSum);
            track.pop_back();
            curSum -= i;
        }
    }
};

@Jing-lun 我忘了 可以直接添加一个 track.size()==k 的判断，就可以做到剪枝操作了。哈哈哈谢谢！🤞

216：

class Solution {
     private List<List<Integer>> res = new LinkedList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    private int trackSum = 0;

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(1, n, k);
        return res;
    }

    public void backtrack(int start, int n, int k) {
        if (k == path.size() && trackSum == n) {
            // 遍历到了第 k 层，trackSun == n，收集
            res.add(new LinkedList<>(path));
            return;
        }
        if (trackSum > n) {
            return;
        }
        for (int i = start ; i <= 9; i++) {
            trackSum += i;
            path.addLast(i);
            backtrack(i + 1, n, k);
            path.removeLast();
            trackSum -= i;
        }
    }
}

对于 排列（元素可重不可复选）的剪枝理解：

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }

1. 如果use[i-1] == true ： 说明 track 里已经有和 nums[i] 相同的元素了，那么 nums[i] 这个元素是可以被选择放进 track 里的。 例如：track = [1, 2] , 可以再放进一个 1 变为 [1, 2, 1]。

2. 如果 use[i-1] == false ： 说明 track 里还没有和 nums[i] 相同的元素，如果有多个与 nums[i] 相同的元素，我们只需把第一个放进track 里，其他的不用管（剪枝）。 所以只有当 i == 0 ，的时候才需要做 add 操作，i > 0 的时候 continue 。（只选第一个） 例如：track = [2] , 外面还有 1 和 1' ，那么我们只需要放第一个 1 进 track = [2, 1] 。[2, 1'] 的情况是要被剪枝的。

感谢！

去重第一时间想到的就是set,哈哈,学到了

关于全排列去重，个人有一个不用排序的解决方案，这里直接使用力扣的签名。

力扣题目地址：https://leetcode.cn/problems/permutations-ii/

代码：

class Solution {
    List<List<Integer>> result=new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        process(nums,new LinkedList<>(),new boolean[nums.length]);
        return result;
    }

    public void process(int[] nums, LinkedList<Integer> track,boolean[] used){
        if(track.size()==nums.length){
            result.add(new LinkedList<>(track));
            return;
        }

        HashSet<Integer> set=new HashSet<>();

        for(int i=0;i<nums.length;i++){
            if(used[i]) continue;
            if(set.contains(nums[i])) continue;
            track.add(nums[i]);
            used[i]=true;
            set.add(nums[i]);
            process(nums,track,used);
            used[i]=false;
            track.removeLast();
        }
    }
}

@wxler 嗯👍，这是一种很直接的去重方法，不过在递归函数中 new 集合会导致每一层递归中都消耗 O(N) 的空间复杂度，恐怕没有排序的方案效率高

排列/组合/子集问题的三种形式，打卡，感谢楼主！

东哥真是我的老师,感谢

377题组合总和 IV 好像是无重可复选的排列问题