两种办法DFS，recursive或者iterative。
一般需要skip重复元素的时候，recursive更容易处理。
Subsets I II
iterative和recursive都比较好想，都是在previous结果的基础上加入新元素生成新的结果加入result。II中处理重复 1，2，2：null，1，2，12，［22，122］－－就是因为对null 1，第一个2已经加过2了，所以第二个2就不用处理null和1了，直接在2和12的基础上处理，生成22，122.
public List<List<Integer>> subsetsWithDup(int[] S) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Arrays.sort(S);
result.add(new ArrayList<Integer>());
int skip = 0, j = 0;
for (int i = 0; i < S.length; i++) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (i > 0 && S[i] == S[i-1])
j = skip;
else
j = 0;
skip = result.size();
for (; j < result.size(); j++) {
List<Integer> tmp = new ArrayList<Integer>(result.get(j));
tmp.add(S[i]);
list.add(tmp);
}
result.addAll(list);
}
return result;
}
Permutations I, II
这个题的iterative是在前面生成的每个结果的每个空档插入新元素：1，2 ＝》 3，1，2；1，3，2；1，2，3
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>());
for (int i = 0; i < num.length; i++) {
List<List<Integer>> newRes = new ArrayList<List<Integer>>();
for (List<Integer> ls: res) {
for (int j = 0; j < ls.size()+1; j++) {
ls.add(j, num[i]);
newRes.add(new ArrayList<Integer>(ls));
ls.remove(j);
}
}
res = new ArrayList<List<Integer>>(newRes);//new object
}
return res;
}
recursive： 在已经生成的串上面重新安排位置：从1，2，。。k位置取出来，然后放在尾部。这个题目的II只会recursive。重复元素只要跳过就好，因为不用重新安排位置。
public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(num.length == 0) return res;
List<Integer> nums = new ArrayList<Integer>();
Arrays.sort(num);
for(int i: num)
nums.add(i);
perm(nums, new ArrayList<Integer>(), res);
return res;
}
public void perm(List<Integer> num, List<Integer> cur, List<List<Integer>> res) {
if(num.isEmpty()) res.add(new ArrayList<Integer>(cur));
else {
for(int i = 0; i < num.size(); i++) {
List<Integer> next = new ArrayList<Integer>(num);
next.remove(i);
cur.add(num.get(i));
perm(next, cur, res);
cur.remove(cur.size()-1);
while(i+1 < num.size() && num.get(i) == num.get(i+1)) {
i++;
}
}
}
}
Permutation Sequence
这个虽然是数学题目，但是需要深入理解permute的本质：每个位置用一个元素会生成（n－1）！个可能元素。所以iterative处理每个位置。
public String getPermutation(int n, int k) {
int index = 1;
List<Integer> nums = new ArrayList<Integer>();
for (int i = 1; i <= n; i++)
nums.add(i);
k--;
k = k % n;
k++;
return perm(nums, new ArrayList<Integer>(), k);
}
private String perm(List<Integer> nums, List<Integer> cur, int k) {
if (k == 1) {
String res = "";
for(int num: nums)
res += String.valueOf(num);
return res;
}
String res = "";
for (int i = 0; i < nums.size(); i++) {
List<Integer> tmp = new ArrayList<Integer>(nums);
tmp.remove(i);
cur.add(nums.get(i));
k-=1;
res = perm(nums, cur, k);
if (k == 1)
break;
cur.remove(cur.size()-1);
}
return res;
}
Combinations n取k个元素
两层循环，外层控制k，内层控制取元素：便利所有可能，就是 j = start + 1; j <= n – k + 1 + i
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (n < k) return result;
result.add(new ArrayList<Integer>());
for (int i = 0; i < k; i++) {
List<List<Integer>> pre = new ArrayList<List<Integer>>();
for (List<Integer> item: result) {
int start = 0;
if (item.size() > 0)
start = item.get(item.size()-1);
for (int j = start + 1; j <= n - k + 1 + i; j++) {
List<Integer> newItem = new ArrayList<Integer>(item);
newItem.add(j);
pre.add(newItem);
}
}
result = new ArrayList<List<Integer>>(pre); // create new here
}
return result;
}
Combination Sum II
典型DFS，走不通就不走了，走通就加入result。
两个要点：
1.dfs里调用下一层dfs的时候，仍然使用i而不是i+1，这是因为可以重复取元素。
2.重复元素直接skip
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> tmpResult = new ArrayList<Integer>();
Arrays.sort(candidates);
dfs(candidates, target, tmpResult, result, 0);
return result;
}
private void dfs(int[] candidates, int target, List<Integer> tmpResult, List<List<Integer>> result, int index) {
if (target == 0) {
result.add(new ArrayList<Integer>(tmpResult));
return;
}
if (index == candidates.length || target < 0) return;
for (int i = index; i < candidates.length; i++) {
int val = candidates[i];
if(i > index && candidates[i-1] == val) continue;
tmpResult.add(val);
dfs(candidates, target - val, tmpResult, result, i+1);
tmpResult.remove(tmpResult.size()-1);
}
}
Sudoku Solver
这个题类似N Queen
不过这里用set保存所有不可用的元素，然后用剩下可用的继续dfs。这次代码比较简洁
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for(int row = 0; row < 9; row++) {
for(int col = 0; col < 9; col++) {
if (board[row][col] != '.')
continue;
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < 9; i++) {
if (board[row][i] != '.')
set.add(board[row][i]-'0');
if (board[i][col] != '.')
set.add(board[i][col]-'0');
}
int startRow = row/3*3, startCol = col/3*3;
for (int j = 0; j < 9; j++) {
if (board[startRow + j/3][startCol + j%3] != '.')
set.add(board[startRow + j/3][startCol + j%3]-'0');
}
for (int k = 1; k < 10; k++) {
if (!set.contains(k)) {
board[row][col] = (char)(k + '0');
if (solve(board))
return true;
}
}
board[row][col] = '.';
return false;
}
}
return true;
}
richdalgo 