leetcode77--组合

1. 题意

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

2. 题解

1. 回溯+减枝

class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;

    void dfs(int cur, int n, int k) {
        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (temp.size() == k) {
            ans.push_back(temp);
            return;
        }
        // 考虑选择当前位置
        temp.push_back(cur);
        dfs(cur + 1, n, k);
        temp.pop_back();
        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }

    vector<vector<int>> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/combinations/solutions/405094/zu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• 我的

class Solution {
public:
    void gen(int begin, int n, int k, vector<vector<int>> &ans, vector<int> &seq) {
        
        if ( seq.size() == k) {
            ans.emplace_back(seq);
            return ;
        }

        for (int i = begin; i <= n; ++i) {
            seq.emplace_back(i);
            gen(i + 1, n, k, ans, seq);
            seq.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        
        vector<int> seq;
        gen(1, n,k,ans,seq);

        return ans;
    }
};

2. 二进制枚举

困难的点在于

• 如何根据字典序顺序生成$k$个1和$n-k$个0的排列
• 如何将二进制的生成排列转换为，序列数的排列

对于问题1，假设当前排列值为$v$,则$next(v)$应为，

1. 若v的最低位为1，从低到高找到最后一个连续的1；将它和它左边的0交换。
   如 n=5,k=3, v=00111 next(v) = 01011
2. 若v的最低位为0，先从低到高过滤掉连续的0, 再找到最高位的连续1, 让它和它左边的0交换；最后再将其低位的1移到最低位。如n=5,k=3; v = 10110, next(v)=11001

我们将1 2对比着看，不难发现情况1实际上是情况2的特殊情况，即没有前面的0要去。

我们可以k位的序列p用1-n来表示第几位上有数字1, 此时的序列也正好对应我们要寻找的答案。
$$len(p)=k,\forall i<k,1\le p_i\le n$$

我们最后做一下转化,连续的1,即对应
$$p[i]+1=p[i+1]$$
而在p表示中，最低位的连续0实际上已经自动去掉了。

• 官解代码

class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;

    vector<vector<int>> combine(int n, int k) {
        // 初始化
        // 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]
        // 末尾加一位 n + 1 作为哨兵
        for (int i = 1; i <= k; ++i) {
            temp.push_back(i);
        }
        temp.push_back(n + 1);
        
        int j = 0;
        while (j < k) {
            ans.emplace_back(temp.begin(), temp.begin() + k);
            j = 0;
            // 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t
            // 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]
            while (j < k && temp[j] + 1 == temp[j + 1]) {
                temp[j] = j + 1;
                ++j;
            }
            // j 是第一个 temp[j] + 1 != temp[j + 1] 的位置
            ++temp[j];
        }
        return ans;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/combinations/solutions/405094/zu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。