77. 组合

77. 组合

回溯

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> tmp;
        vector<vector<int>> ret;
        backTrack(n, k, 1, tmp, ret);
        return ret;
    }
private:
    void backTrack(int n, int k, int start, vector<int>& tmp, vector<vector<int>>& ret)
    {
        if(n - start + 1 < k - tmp.size()) // 剪枝
            return;
        if(tmp.size() == k)
        {
            ret.push_back(tmp);
            return;
        }
        for(int i = start; i <= n; ++i)
        {
            tmp.push_back(i);
            backTrack(n, k, i + 1, tmp, ret);
            tmp.pop_back();
        }
    }
};

字典序法太烦了

引用@老黑不黑的评论

btw我又读了十几遍，总算搞清楚算法了。简单来说就是一开始把所有的1放在尾部，比如00111这样，然后按顺序把1往前移动。如果所有的1都在最前头了，比如11100，就留一位1，其余的全部移到末尾，比如10011，然后再重复这个操作，直到所有的1都“被”留在了最前面，即11100，便完成了全部穷举。其实是很直观的一个思路。不知道为什么，一加上数学语言的buf之后，就让我愣是横竖也看不懂过程了。LC-CN还算有良心，加了个小贴士 这个方法理解起来比「方法一」复杂，建议读者遇到不理解的地方可以在草稿纸上举例模拟这个过程。