Iterative Version


  • 4
    Y
    class Solution {
    public:
        vector<vector<int> > combine(int n, int k) {
            int cur=0;
            vector<int> v(k,0);
            vector<vector<int> > ans;
            while (cur>=0) {
                if (cur==k) {
                    ans.push_back(v);
                    --cur;
                    continue;
                }
                int val=v[cur]+1;
                if (cur>0) {
                    val=max(val,v[cur-1]+1);
                }
                if (val<=n) {
                    v[cur++]=val;
                } else {
                    v[cur--]=0;
                }
            }
            return ans;
        }
    };

  • 3
    J

    Here is mine:

    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> result;
            if (n < 1 || k < 1 || k > n) return result;
            vector<int> v = {1};
            bool toNext = false;
            while (!v.empty() && v.front() <= n - k + 1) {
                if (v.size() == k) {
                    result.push_back(v);
                }
                int x = v.back();
                if (x < n) {
                    if (v.size() == k || toNext) {
                        v.pop_back();
                        toNext = false;
                    }
                    v.push_back(x + 1);
                } else {
                    v.pop_back();
                    toNext = true;
                }
            }
            return result;
        }
    };
    

    Edit: It will only choose the numbers bigger than the numbers in the vector to make a combination, so it can avoid duplicates. E.g.

    1 2 3 4, 2
    
    1 2, 1 3, 1 4,
    2 3, 2 4
    3 4
    

    And it will quit the loop when there is no enough numbers to choose from the list.


  • 0
    W

    Cool. Similar idea with mine, more concise code.


  • 0
    E

    Could you explain what's the meaning of v.front() <= n - k + 1 ? Thanks.


  • 0
    J

    :D Sure. It is not a necessary statement, but it can reduce the unnecessary loops. Because I only choose the bigger numbers to combine with the numbers in the vector so as to avoid duplicates, then I can tell when it is imposible to get enough numbers.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.