My shortest c++ solution,using dfs


  • 39
    N

    my idea is using backtracking ,every time I push a number into vector,then I push a bigger one into it;
    then i pop the latest one,and push a another bigger one...
    and if I has push k number into vector,I push this into result;

    this solution take 24 ms.

    class Solution {
    public:
        vector<vector<int> > combine(int n, int k) {
            vector<vector<int> >res;
            if(n<k)return res;
            vector<int> temp(0,k);
            combine(res,temp,0,0,n,k);
            return res;
        }
        
        void combine(vector<vector<int> > &res,vector<int> &temp,int start,int num,int n ,int k){
            if(num==k){
                res.push_back(temp);
                return;
            }
            for(int i = start;i<n;i++){
                temp.push_back(i+1);
                combine(res,temp,i+1,num+1,n,k);
                temp.pop_back();
                }
            }
    };

  • 30
    J

    How about this, avoid calling push_back() and pop_back() too often.

    class Solution {
    public:
        vector<vector<int> > combine(int n, int k) {
            v.resize(k);
            dfs(1, n, k);
            return r;
        }
    private:
        vector<vector<int> > r;
        vector<int> v;
        void dfs(int i, int n, int k) {
            while (i <= n) {
                v[v.size() - k] = i++;
                if (k > 1)
                    dfs(i, n, k - 1);
                else
                    r.push_back(v);
            }
        }
    };

  • 0
    S

    according the backtracking idea!


  • 0
    H

    nice solution. Maybe v.size() can be change to new variable klen while klen=v.size().


  • 4
    H

    Improved the dfs method, using pruning when dfs. takes 8 ms. i <= (n-k+1) replace i<=n.

    Because our dfs result is a sorted array.

    if n = 5, k = 3;
    we select i = 1 at first, v =[1, X, X], X means need to fill using dfs.

    then we iterate i, i = 2, v = [2, X, X]
    i = 3, v = [3, X, X].

    now we need stop to search. if v= [4, X, X], we can't find 2 number greater than 4, and in the range [1, 5];

    class Solution {
    public:
        vector<vector<int> > combine(int n, int k) {
            // dfs method
            if(k == 0 || n == 0 || n<k)
                return result;
            v.resize(k);
            combinecore(1, n, k);
            return result;
        }
        
        void combinecore(int startnum, int n, int k) {
            int i = startnum;
            while(i<=(n-k+1)) {
                v[v.size()-k] = i;
                i++;
                if(k>1)
                    combinecore(i, n, k-1);
                else
                    result.push_back(v);
            }
        }
    private:
        vector<int> v;
        vector<vector<int> > result;
    };
    

  • 0
    H

    why "vector<int> temp(0, k)" ? but not "vector<int> temp".


  • 0
    T

    Nice code , very good!!!!!


  • 0
    J

    Thank you for sharing your solution. This is my java version.

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(res,1,n,k,k,new ArrayList<Integer>(k));
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, int i, int n, int k, int cap, List<Integer> list) {
        while(i<=n) {
            List<Integer> copy = new ArrayList<Integer>(list);
            copy.add(cap - k, i++);
            if(k>1)
                backtrack(res,i,n,k-1,cap,copy);
            else {
                res.add(copy);
            }
        }
    }

  • 0
    N

    What would be time complexity for this solution ?


  • 0
    T

    n to the power of 3


Log in to reply
 

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