77. Combinations ---M !

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
 
Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
 
Constraints:
1 <= n <= 20
1 <= k <= n

A:
#####递归#############

class Solution:
    def combine(self, n: int, k: int):
        return self.helper(1,n,k)
    
    def helper(self, a: int, b: int, len: int):
        if  b - a + 1 < len or len <= 0:
            return []
        if len == 1:
            return [[i] for i in range(a,b+1)]
        res = []
        for i in range(a,b+1):
            nextList = self.helper(i+1,b, len - 1)
            for tmp in nextList:
                tmp.insert(0, i)
            res.extend(nextList)
        return res

#####循环#############

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        for kk in range(1,k+1):
            if kk ==1:
                res = [ [t] for t in range(1,n+1)]
            else:
                newRes = []
                for tmp in res:
                    for lastVal in range(tmp[-1]+1, n+1):
                        newTmp = tmp.copy()
                        newTmp.append(lastVal)
                        newRes.append(newTmp)
                res = newRes
        return res

------4th pass----------是每次分两种情况，
1):   取了第一个数字，
2):   不取第一个数字---------------

class Solution {

public:

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

vector<int> V;

for(int i =1;i<=n;i++){

V.emplace_back(i);

}

vector<vector<int>> res;

vector<int> selected;

helper(V, res, selected, 0, k);

return res;

}

private:

void helper(vector<int>& V,vector<vector<int>>& res, vector<int>& selected, int start, int k ){

if(k == 0){

res.push_back(selected);

return;

}

int n = V.size();

if(start >= n)

return;

// not use

helper(V, res, selected, start+1, k);

selected.push_back(V[start]);

helper(V, res, selected, start+1, k-1);

selected.pop_back();

}

};

后来，又仔细想了想，其实不需要vector，而只是需要前后的值，就行。

修改如下

class Solution {

public:

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

vector<vector<int>> res;

vector<int> selected;

helper(1, n, res, selected, k);

return res;

}

private:

void helper(int start, int n,vector<vector<int>>& res, vector<int>& selected, int k ){

if(k == 0){

res.push_back(selected);

return;

}

if(start > n)

return;

helper(start+1,n, res, selected, k);// not use

selected.push_back(start);

helper(start+1,n, res, selected, k-1);

selected.pop_back();

}

};

然后再想了想，其实也不需要selected来记录已经走的的。

直接加上后一步的结果可以的 （然而会 memory limit exceeded)

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        return helper(1, n, k);
    }
private:
    vector<vector<int>> helper(int start, int end, int k ){
        vector<vector<int>> res;
        if( k == 0){
            res.push_back({});
            return res;
        }
        if( k >  end -start +1)
            return res;
        res = helper(start+1, end, k);
        auto res2 = helper(start+1, end, k-1);
        for(auto &v : res2){
            v.push_back(start);
        }
        res.insert(res.end(), res2.begin(), res2.end());
        return res;
    }
};

Mistakes:
这道题目的，可能犯得错误，就在于k和start,end的比较。



Learned:

----------------3rd Pass--------------------思路想的一样，但是， 犯了个错误， 就是 在for 循环里， 每次combine了一个 -------------靠，没有犯错，是不自信，在Eclipse中先运行拉下，结果打印的时候， 参数成了那个all了。 白调试了20分钟。

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        return helper(1,n,k);
    }
    private List<List<Integer>> helper(int start, int end, int k ){
        List<List<Integer>> all = new LinkedList<List<Integer>>();
        if(k==1){
            for(int i=start;i<=end;i++){
                List<Integer> list = new LinkedList<Integer>();
                list.add(i);
                all.add(list);
            }
        }else{
            for(int i =start;i<=end-k+1;i++){
                List<List<Integer>> oneLess = helper(i+1,end,k-1);
                for(List<Integer> al : oneLess)
                    al.add(0,i);
                all.addAll(oneLess);
            }
        }
        return all;
    }
}