Subsets & Permutation

Combination 类问题最重要的是 去重， dfs() 函数里带一个 index 参数可以很好的解决这个问题。

Combination

在这个问题里，k = depth of tree，n = branching factor.

在这个具体问题里，因为解是单调连续增加的序列(Monotonically increasing sequence) 1,2..n，去重方法上可以稍微取巧一些：dfs里增加一个“前一个元素”的参数，每一层递归只考虑比上一个元素大的值。

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();

        if(k > n || n < 1) {
            return result;
        } 

        List<Integer> path = new ArrayList<>();
        helper(n, k, result, path, 1);
        return result;
    }

    public void helper(int n, int k, List<List<Integer>> result, 
                        List<Integer> path, int index) {
        if(path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = index; i <= n; i++) {
            path.add(i);
            // 为了不重复，每一层递归只考虑更大的元素
            helper(n,k,result,path,i + 1);
            path.remove(path.size() - 1);
        }
    }
}

Subsets

这一题等于递归搜索的时候记录所有的中间结果。为了去重，用一个index记录当前层取到的数的位置，每一层从下一个数开始取。

Permutations

如何去重。 简单的方法就是用arraylist自带的contians来判断，缺点是时间复杂度比较高，如果输入的集合比较大的话就会很慢，但是因为是permutation所以输入集合一般不会特别大。

Permutations II

和Permutation的不同之处在于，输入的集合可能会有重复的数，如何去重？

用一个flag数组去标记每个数是否用过，如果是用过的数直接continue。 还有就是如果相邻的两个数（two adjacent numbers）是一样的也要跳过。

Lexicographical Numbers

given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

字典序问题，而且是生成数字，所以是搜索问题，所以其实是一道dfs问题

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        // sort by the significant digit
        // use less time and space means using bit manipulate
        List<Integer> result = new ArrayList<>();
        if(n < 1) {
            return result;
        }

        // from the most significant digit
        // if same next digit
        // so it's dfs
        //     1
        //   /   \
        //  10...19
        // base case is the number wouldn't larger than n

        for(int i = 1; i < 10; i++) {
            dfs(i, n, result);
        }

        return result;
    }

    private void dfs(int cur, int n, List<Integer> result) {
        if(cur > n) {
            return;
        }
        // error-prone
        // java pass-by-value
        // no bracktracking, so put the add operation out
        result.add(cur);
        for(int i = 0; i < 10; i++) {
            // if result.add(cur) in here, each loop will add cur.
            if(cur * 10 + i > n) break;
            dfs(cur * 10 + i, n, result);
        }
    }
}

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Idea

这一题的输入是Set，每个元素可以不限次的取,新一层 dfs 迭代的时候要从上一层一样的 index 开始。然而还是要注意不要去看 index 之前的元素。

退出条件，target <= 0

Combination Sum 2

Each number in C may only be used once in the combination.

每个数只能取一次，所以取完一个数以后，到下一层的时候需要i+1。 为了避免一样的元素反复取，需要检查相邻的元素是否一样。

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

helper(n,k,result,path,start)

start 的目的是保证了unique