Subsets, Combination 与 Permutation
Combination 类问题最重要的是去重， dfs() 函数里带一个 index 参数可以很好的解决这个问题。
顺序问题中有“单序列”和“全序列”顺序，分别对应一个序列中元素的顺序和整个序列中子序列顺序。可以通过子序列翻转或者全局翻转操作，利用两次翻转相互抵消的特点解决序列顺序问题。
用数学语言描述就是： ' 代表 inverse
S = ABCD
S' = D'C'B'A'
(A'B'C'D')' = DCBA
LintCode - Combinations
Combination 类问题是典型的搜索问题，除了 DFS + backtracking 之外，combination 里最重要的就是“去重”，怎么让自己的搜索树不回头地往前走。
在这个问题里，k = depth of tree，n = branching factor. 当然因为解个数的唯一性，不是每个节点的 fan out 都一样。
在这个具体问题里，因为解是单调连续增加的序列 1,2..n，去重方法上可以稍微取巧一些：dfs里增加一个“前一个元素”的参数，每一层递归只考虑比上一个元素大的值。
public class Solution {
/**
* @param n: Given the range of numbers
* @param k: Given the numbers of combinations
* @return: All the combinations of k numbers out of 1..n
*/
public List<List<Integer>> combine(int n, int k) {
// write your code here
List<List<Integer>> rst = new ArrayList<List<Integer>>();
dfs(rst, new ArrayList<Integer>(), n, k, 0);
return rst;
}
private void dfs(List<List<Integer>> rst, List<Integer> list, int n, int k, int prev){
if(list.size() == k) {
rst.add(new ArrayList<Integer>(list));
//list.remove(list.size() - 1);
}
for(int i = prev + 1; i <= n; i++){
if(list.contains(i)) continue;
list.add(i);
dfs(rst, list, n, k, i);
list.remove(list.size() - 1);
}
}
}
LintCode - Combination Sum
相似的题有一样的思路，不同的题有不同的坑。
为了去重的考虑，还是要 dfs 参数里带 index. 这里有一个细微的差别，因为同一个数可以用多次，新一层 dfs 迭代的时候要从上一层一样的 index 开始。然而还是要注意不要去看 index 之前的元素。
同时因为同一个元素可以用多次，必须要有一个有效的 dfs 终止条件，不然搜索树会永远一直加下去。。考虑到给定条件是“所有元素都为正整数”，我们就可以在当前 sum > target 的时候终止搜索。如果可以重复元素又有负数的话，这题就没法做了。
OJ 要求每一个结果都是 sorted list，稍微有点二逼，注意不能直接 sort 函数里的 list，因为会打乱其他 dfs 中的结果 （same memory address pass by value），要去新建一个 list copy 再调用 Collections.sort()
public class Solution {
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// write your code here
List<List<Integer>> rst = new ArrayList<List<Integer>>();
if(candidates == null || candidates.length == 0) return rst;
dfs(rst, new ArrayList<Integer>(), candidates, target, 0, 0);
return rst;
}
private void dfs(List<List<Integer>> rst, List<Integer> list, int[] candidates,
int target, int curSum, int index){
if(curSum > target) return;
if(curSum == target){
List<Integer> newList = new ArrayList<Integer>(list);
Collections.sort(newList);
rst.add(newList);
return;
}
for(int i = index; i < candidates.length; i++){
list.add(candidates[i]);
curSum += candidates[i];
dfs(rst, list, candidates, target, curSum, i);
curSum -= candidates[i];
list.remove(list.size() - 1);
}
}
}
LintCode - Subsets
class Solution {
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
// write your code here
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
if(nums == null || nums.length == 0) return rst;
Arrays.sort(nums);
dfs(rst, new ArrayList<Integer>(), nums, 0);
return rst;
}
private void dfs(ArrayList<ArrayList<Integer>> rst,
List<Integer> list, int[] nums, int index){
rst.add(new ArrayList<Integer>(list));
for(int i = index; i < nums.length; i++){
list.add(nums[i]);
dfs(rst, list, nums, i + 1);
list.remove(list.size() - 1);
}
}
}
LintCode - Permutations
都是简单套路和小变形。这次每轮dfs都考虑所有元素（所以不用传 index 参数了），传个 boolean array 只挑没用过的数字就可以了。
class Solution {
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
// write your code here
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
if(nums == null || nums.size() == 0) return rst;
boolean[] used = new boolean[nums.size()];
dfs(rst, new ArrayList<Integer>(), nums, used);
return rst;
}
private void dfs(ArrayList<ArrayList<Integer>> rst, List<Integer> list,
ArrayList<Integer> nums, boolean[] used){
if(list.size() == nums.size()){
rst.add(new ArrayList<Integer>(list));
return;
}
for(int i = 0; i < nums.size(); i++){
if(used[i]) continue;
list.add(nums.get(i));
used[i] = true;
dfs(rst, list, nums, used);
used[i] = false;
list.remove(list.size() - 1);
}
}
}
LintCode - Permutations II
基本没啥区别。只加了新的一行，确保下在一个 dfs 返回，回溯结束之后，下一个数别选一样的就行了。
class Solution {
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums){
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
if(nums == null || nums.size() == 0) return rst;
boolean[] used = new boolean[nums.size()];
Collections.sort(nums);
dfs(rst, new ArrayList<Integer>(), nums, used);
return rst;
}
private void dfs(ArrayList<ArrayList<Integer>> rst, List<Integer> list,
ArrayList<Integer> nums, boolean[] used){
if(list.size() == nums.size()){
rst.add(new ArrayList<Integer>(list));
return;
}
for(int i = 0; i < nums.size(); i++){
if(used[i]) continue;
list.add(nums.get(i));
used[i] = true;
dfs(rst, list, nums, used);
used[i] = false;
list.remove(list.size() - 1);
while(i < nums.size() - 1 && nums.get(i + 1) == nums.get(i)){
i ++;
}
}
}
}
Beautiful Arrangement
变种：改backtracking的判断条件就可以。注意用cur.size()+1而不是i
在判断b是不是a的因子的时候，可以利用a/b*b==a判断。
public class Solution {
int count =0;
public int countArrangement(int N) {
int[] list = new int[N]; boolean[] visited = new boolean[N];
for(int i=1;i<=N;i++)
list[i-1]=i;
dfs(list, visited, new ArrayList<Integer>());
return count;
}
public void dfs(int[] list, boolean[] visited, List<Integer> cur){
if(cur.size()==list.length){
count++;
//System.out.println(Arrays.toString(cur.toArray()));
}
for(int i=1;i<=list.length;i++){
if(!visited[i-1]&&((cur.size()+1)/list[i-1]*list[i-1]==(cur.size()+1) || list[i-1]/(cur.size()+1)*(cur.size()+1)==list[i-1])){
visited[i-1] = true;
cur.add(list[i-1]);
dfs(list, visited, cur);
cur.remove(cur.size()-1);
visited[i-1] = false;
}
}
}
}