77. Combination

Given two integersnandk, 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],
]

思路：万能解法

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        int[] arr = new int[n];
        for (int i = 0; i<n; i++){
            arr[i] = i+1;
        }
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        traceback(res, temp, arr, k, 0);
        return res;
    }

    public void traceback(List<List<Integer>> res, List<Integer> temp, int[] arr, int k, int start){
        if(temp.size()==k){
            res.add(new ArrayList<Integer>(temp));
        }

        if (temp.size()>k){
            return;
        }

        for (int i=start;i<arr.length;i++){
            if (temp.contains(arr[i])) continue;
            temp.add(arr[i]);
            traceback(res,temp,arr,k,i+1);
            temp.remove(temp.size()-1);
        }
    }
}