77. Combinations

Problem:

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路：
这题的思路很难直接用语言表述，建议看代码，然后再纸上将其每一步运行的结果一步步写出，就好理解了。
大致的思路是这样的，它是按照从右往左来试探的。首先确定好低位之后，最高位的值如果不超过n（高位低位以数组的下标来理解）则满足条件。如果最高位的值超过n，则说明次高位的值还有增加的空间，调整次高位的值（++），再让最高位的值等于次高位的值然后依次往上递增，看是否满足条件。如果较高位的值都超过了n，则会一直往低位去寻找，如果每一位的值都超过了n，那么最好寻找的下标i会小于0，从而不满足while循环的条件，循环终止，重新开始。

Solution:

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    int i = 0;
    vector<int> p(k, 0);
        
    while (i >= 0) {
        p[i]++;
        if (p[i] > n) 
             --i;
        else if (i == k-1) 
            res.push_back(p);
        else {
            ++i;
            p[i] = p[i-1];
        }
    }
        
    return res;            
}

性能：
Runtime: 76 ms  Memory Usage: 11.8 MB

扩展：
有兴趣的同学可以运行下面的代码（来自于LeetCode）来理解上面代码的思路，验证流程是否正确，确实挺佩服老外的钻研精神。

#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;
}