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