Leetcode: Combinations

77. Combinations

My Submissions

Total Accepted: 61469 Total Submissions: 189601 Difficulty: Medium

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

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Subscribe to see which companies asked this question

Hide Tags

 Backtracking

Hide Similar Problems

 (M) Combination Sum (M) Permutations

```````````````````````````````````````````````````````````````````````````````

Backtracking:

Similar as Combination Sum I, II, III. 

///////////////////////////////////////////////

//CODES

class Solution {

public:

   void backTrac(vector<vector<int>>& res, int n, int k, vector<int>& tmp, int len, int i){

       if(len==k) {res.push_back(tmp); return;}

       else{

           for (;i<n;i++){

               tmp.push_back(i+1);

               len++;

               backTrac(res, n, k, tmp, len, i+1);

               len--;

               tmp.pop_back();

           }

           return;

       }

   }

    vector<vector<int>> combine(int n, int k) {

        vector<vector<int>> res;

        vector<int> tmp;

        int len=0, i=0;

        backTrac(res, n, k, tmp, len, i);

        return res;

    }

};