CPP solution: traverse from [1,2] to [3,4]


  • 0
    L
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> ans;
            if (k > n)
                    return ans;
    
            vector<int> v(k, 0);
            for (int iii = 0; iii < k; iii++)
                    v[iii] = iii + 1;
            ans.push_back(v);
    
            while (1) {
                    bool finish = true;
                    for (int iii = 0; iii < v.size(); iii++) {
                            if (v[iii] != n - k + iii + 1) {
                                    finish = false;
                                    break;
                            }
                    }
                    if (finish) {
                            return ans;
                    }
    
                    for (int iii = v.size() - 1; iii >= 0; iii--) {
                            if (v[iii] != n - k + iii + 1) {
                                    v[iii]++;
                                    for (int jjj = iii + 1; jjj < v.size(); jjj++) {
                                            v[jjj] = v[jjj - 1] + 1;
                                    }
                                    ans.push_back(v);
                                    break;
                            }
                    }
    
            }
        }
    };

  • 0
    L

    Here are my solutions:

    https://github.com/loverszhaokai/ALG/blob/master/src/combinations.cc

    Feel free to give me any advice.


  • 2

    Wrote my own version. It's quite similar but also somewhat different.

    vector<vector<int>> combine(int n, int k) {
        vector<int> comb;
        for (int i=1; i<=k; i++)
            comb.push_back(i);
        vector<vector<int>> combs(1, comb);
        while (true) {
            int i = k - 1;
            while (i >= 0 && comb[i] - i == n - k + 1)
                i--;
            if (i < 0)
                return combs;
            comb[i]++;
            while (++i < k)
                comb[i] = comb[i-1] + 1;
            combs.push_back(comb);
        }
    }
    

    And a Python version:

    def combine(self, n, k):
        comb = range(1, k+1)
        combs = [comb[:]]
        while True:
            i = k - 1
            while i >= 0 and comb[i] - i == n - k + 1:
                i -= 1
            if i < 0:
                return combs
            comb[i:] = range(comb[i]+1, comb[i]+1+k-i)
            combs += comb[:],
    

  • 0

    Why iii instead of the usual i?


  • 0
    L

    Oh, both are ok. I use iii instead of i just to make it clear, since i, j, k ... are always confusing.


  • 0
    L

    Also, iii is easy for searching than i.


  • 0
    L

    Very good! Your solution is more compact!

    After looked through your solution, I found that mine was wasting time on searching the last index which was not the max value of its position.

    I think your solution will be better if you can save some time on initing com.

    vector<vector<int>> combine(int n, int k) {
        vector<int> comb(k, 0);
        for (int i=1; i<=k; i++)
            comb[i - 1] = i;
        ...
    }

  • 0

    I thought about doing that, don't remember why I didn't. I don't think it'll be noticeably faster, though, if at all. I mean, it's just the initialization.


  • 0

    Ah, yes, for searching it's definitely nice :-). Though a good IDE should be able to find exactly every occurrence even if it's just i.


  • 0
    L

    Yes it has little impact.


  • 0
    L

    Yes, a good IDE will be, such as visual studio 2013. But I use emacs. :)


  • 0

    Heh, yeah, I currently use Notepad++ :-)


Log in to reply
 

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