[leetcode] Combinations | 给数字n和k，求所有由1～n组成的长度为k的combination

Posted by: lexigrey on: October 9, 2013

• In: leetcode
• Leave a Comment

If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
趁热打铁，这个题和上两道相比简单了不少，因为是固定长度所以不用stack了，用int[]加一个position variable。每次在这个pos上一个一个试数，每确定一个就在下一个pos处recurse。

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  if (k <= 0 || n < 1)
    return result;
  populateResult(1, n, 0, result, new int[k]);
  return result;
}
private void populateResult(int startNum, int endNum, int pos, 
            ArrayList<ArrayList<Integer>> result, int[] path) {
  if (pos == path.length) {
    ArrayList<Integer> combination = new ArrayList<Integer>();
    convertArrayToList(path, combination);
    result.add(combination);
    return;
  }
  for (int i = startNum; i <= endNum; i++) { //i is using which number
    path[pos] = i;
    populateResult(i + 1, endNum, pos + 1, result, path); //use next 
                                            //number on next position
    //as i++, use next number on same position
  }
}

Tags: subsets/permutation, 固定解法