LeetCode 77 Combinations

    
        标签：
        
            回溯法
        
            LeetCode
        
    发布于：2020-06-12 10:30:58
    编辑于：2022-02-22 15:53:37
    浏览量：1192

概述

https://leetcode.com/problems/combinations/

套回溯法解题框架

思路分析：如果是我们手写组合，我们肯定是按照顺序来写的，注意到后续选择的数字一定大于之前的数字。也就是说我们需要一个值来记录当前可以选择的数字的区间的起点。

class Solution {
public:
    vector<vector<int>> ans;
    int n;
    int k;
    vector<vector<int>> combine(int n, int k) {
        this->n = n;
        this->k = k;
        vector<int> v;
        backtrack(v, 1);
        return ans;
    }
    
    void backtrack(vector<int>& v, int start) {
        if(v.size()==k) {
            ans.push_back(v);
            return;
        }
        
        for(int i=start;i<=n;i++) {
            v.push_back(i);
            backtrack(v, i+1);
            v.pop_back();
        }
    }
};

迭代形式的解

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        int i = 0;
        vector<int> p(k, 0);
        while (i >= 0) {
            p[i]++; // 使用当前位置上的下一个选择
            if (p[i] > n) --i; // 当前位置上可选的数字已经用尽，回退到上一位
            else if (i == k - 1) result.push_back(p); // 找到了一个解，存起来
            else {
                ++i; // 换下一个位置
                p[i] = p[i - 1]; // 下一个位置的起始值比当前位置的值大一，下次循环开始后会把一补上的
            }
        }
        return result;
    }
};

答案出处：https://leetcode.com/problems/combinations/discuss/26992/Short-Iterative-C%2B%2B-Answer-8ms

2022年2月22日的解法

class Solution {
public:
    vector<vector<int>> ans;
    int n, k;
    vector<vector<int>> combine(int n, int k) {
        this->n = n;
        this->k = k;
        vector<int> l;
        backtrack(l, 1, 0);
        return ans;
    }
    
    void backtrack(vector<int>& l, int s, int idx) {
        if (idx == k) {
            ans.push_back(l);
            return;
        }
        for (int i = s; i <= n; i ++) {
            l.push_back(i);
            backtrack(l, i + 1, idx + 1);
            l.pop_back();
        }
    }
};

Links: LeetCode-77-Combinations