77. Combinations

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> out;
        dfs(n, k, 1, out, res);
        return res;
    }
    void dfs(int n, int k, int level, vector<int>& out, vector<vector<int>>& res) {
        if (out.size() == k) res.push_back(out);
        //注意这里是out.size() ==k
        // 还有k - out.size()个空位, 所以,[i...n]中至少要有k-out.size()个元素
        //n-i+1>=(k-out.size())
        // i最多为 n - (k-out.size()) + 1
        for (int i = level; i <= n - (k-out.size()) + 1; ++i) {
        //注意这里是i = level
            out.push_back(i);
            dfs(n, k, i + 1, out, res);
            //注意这里是i＋1 cur pos 向前一位call dfs
            //也可以想象为刚加进去了i，后面一位要从i＋1开始
            out.pop_back();
        }
    }
};

举例n=4,k=2
1，2
1，3
1，4
此处返回最外层的level，start是1但是i变成2了
2，3
2，4
3，4

Incremented element at index 0
[1, 0]
Moved index to the right, and copied the value from the left
[1, 1]
Incremented element at index 1
[1, 2]
Combination found!
Added [1, 2] as an answer!
Incremented element at index 1
[1, 3]
Combination found!
Added [1, 3] as an answer!
Incremented element at index 1
[1, 4]
Combination found!
Added [1, 4] as an answer!
Incremented element at index 1
[1, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[2, 5]
Moved index to the right, and copied the value from the left
[2, 2]
Incremented element at index 1
[2, 3]
Combination found!
Added [2, 3] as an answer!
Incremented element at index 1
[2, 4]
Combination found!
Added [2, 4] as an answer!
Incremented element at index 1
[2, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[3, 5]
Moved index to the right, and copied the value from the left
[3, 3]
Incremented element at index 1
[3, 4]
Combination found!
Added [3, 4] as an answer!
Incremented element at index 1
[3, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[4, 5]
Moved index to the right, and copied the value from the left
[4, 4]
Incremented element at index 1
[4, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[5, 5]
n exceeded at 0, moving index to the left
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string toString(vector<int> v) {
    string ans = "[";
    for (int i: v) {
        ans += i + '0';
        ans += ", ";
    }
    ans = ans.substr(0, ans.length() - 2) + "]";
    return ans;
}

string toString(vector<vector<int>> v) {
    string ans = "[";
    for (vector<int> i: v) {
        ans += toString(i);
        ans += ", ";
    }
    ans = ans.substr(0, ans.length() - 2) + "]";
    return ans;
}

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> c(k, 0); // vector of length k, all 0s
        int i = 0;
        while (i >= 0) {
            // Increment element at index i
            c[i]++;
            cout << "Incremented element at index " << i << endl;
            cout << toString(c) << endl;

            /* Move index to the left if the element
             * at index i has exceeded n.
             */
            if (c[i] > n) {
                i--;
                cout << "n exceeded at " << i+1 << ", moving index to the left" << endl;
            }

            /* If the index is at the end of the vector
             * c, then (because the other conditions are
             * obeyed), we know we have a valid combination,
             * so push it to our ans vector<vector<>>
             */
            else if (i == k - 1) {
                ans.push_back(c);
                cout << "Combination found!" << endl;
                cout << "Added " << toString(c) << " as an answer!" << endl;
            }

            /* Move index to the right and set the
             * element at that index equal to the
             * element at the previous index.
             * 
             * Because of the increment at the beginning
             * of this while loop, we ensure that the
             * element at this index will be at least
             * one more than its neighbor to the left.
             */
            else {
                i++;
                c[i] = c[i - 1];
                cout << "Moved index to the right, and copied the value"
                << " from the left" << endl;
                cout << toString(c) << endl;
            }
        }
        return ans;
    }
};

int main() {
    Solution sol;
    cout << toString(sol.combine(4, 2)) << endl;
    return 0;
    }

results matching ""

    No results matching ""