Lexi's Leetcode solutions

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

这个思路本来很简单，如果用recursion来enumeration的话，即用set，每次第i个位置用了set的第j个元素，然后set remove j, recurse on i + 1。非常straight forward的做法，但是用java这么做有好几个问题：

• 如果input有重复，如aabc，set没法处理同时存在2个a的情况。
• 在recurse on set的每个元素的时候，因为for循环是interate thru set itself，但里面还有set.add(), set.remove这些改变set本身的语句，所以会有modify iterator exception。还得弄个copy先。
• 代码巨长。越写越没信心。

所以还是CC150上的另一种思路：每次取一个元素，对于之前（上一层循环的list结果）的每个permutation, 在能插的地方就插这个新元素，然后生成新的permutation，放入这一层的结果。这样代码相对简单，而且不用recursion。有几个要点：

1. 最开始要传一个空的permutation进去，否则没处可insert第一个元素。
2. 这种做法不能防止duplication（1212可能有好几种insert成它的方法）。

public ArrayList<ArrayList<Integer>> permute(int[] num) {
  ArrayList<ArrayList<Integer>> lastLayer = new ArrayList<ArrayList<Integer>>();
  lastLayer.add(new ArrayList<Integer>());
  for (int i = 0; i < num.length; i++) {
    ArrayList<ArrayList<Integer>> newLayer = new ArrayList<ArrayList<Integer>>();
    for (int j = 0; j < lastLayer.size(); j++) {
      ArrayList<Integer> curr = lastLayer.get(j);
      insertEverywhere(curr, num[i], newLayer);
    }
    lastLayer = newLayer;
  }
  return lastLayer;
}
private void insertEverywhere(ArrayList<Integer> curr, int num, ArrayList<ArrayList<Integer>> newLayer) {
  for (int i = 0; i <= curr.size(); i++) {
    ArrayList<Integer> newList = new ArrayList<Integer>(curr);
    newList.add(i, num);
    newLayer.add(newList);
   }
}