77 Combinations

Q:
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],
]

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):   不取第一个数字---------------

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>> ll  = new LinkedList();
        if(k<=0 || k>(end-start+1))
            return ll;
        if(k==1){
            for(int i = start;i<=end;i++){
                List<Integer> l = new LinkedList();
                l.add(i);
                ll.add(l);
            }
            return ll;
        }
        for(List<Integer> tmp : helper(start+1,end,k-1)){
            tmp.add(0,start);
            ll.add(tmp);
        }
        ll.addAll(helper(start+1,end,k));
        return ll;
    }
}

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



Learned:
1:    当 all的类型是ArrayList<ArrayList<Integer>>的时候，下面的语句
                all.add(new ArrayList<Integer>(i));
所加入的都是空的ArrayList. 不知道为什么？？？？ 因此要一个个地加。 
一个constructor，当是int 参数时，是给定的initial capacity.

public class Solution {
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
    return combine(1, n, k);
}
public ArrayList<ArrayList<Integer>> combine(int start, int end, int k) {
    ArrayList<ArrayList<Integer>> all = new  ArrayList<ArrayList<Integer>>();
    if(end - start +1 < k  )
        return all;
    // each time, we shrink the size of k
    
    
   if( k == 1){ // 
         for(int i =start; i <= end;i++){
            ArrayList<Integer> al = new  ArrayList<Integer>();
            al.add(i);
            all.add(al);
         }
         return all;
    }else{
         all = combine(start+1,end,k-1);
         for(ArrayList<Integer> al: all) // all with start, 
            al.add(0,start);
        // all without start
         ArrayList<ArrayList<Integer>> newAll = combine(start+1,end,k);
         all.addAll(newAll);
         return all;
    }
}

}

----------------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;
    }
}