枚举法

DFS + Backtracking 的搜索量很大。如果每次 DFS 之前都要进行条件检查的话，优化条件函数可以显著提升程序速度。如 N-Queens 和 Palindrome Partitioning 还有 Sudoku Solver

Generate Parentheses， 限制条件是右括号的数量只能小于等于左括号的数量

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        if (n <= 0) {
            return result;
        }

        StringBuffer sb = new StringBuffer();
        dfs(result, sb, 0, 0, n);
        return result;
    }

    private void dfs(List<String> result, StringBuffer sb, int left, int right, int n) {
        if (left == n && right == n) {
            result.add(sb.toString());
            return;
        }

        if (left < n) {
            sb.append("(");
            dfs(result, sb, left + 1, right, n);
            sb.setLength(sb.length() - 1);
        }

        if (right < left && right < n) {
            sb.append(")");
            dfs(result, sb, left, right + 1, n);
            sb.setLength(sb.length() - 1);
        }
    }
}

Restore IP Addresses, 限制条件是对于大于一位的substring, 第一位不能’0'， 另外数字不能大于255.

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() < 4 || s.length() > 12) {
            return result;
        }

        StringBuffer sb = new StringBuffer();
        dfs(result, sb, s, 0);
        return result;
    }

    private void dfs(List<String> result, StringBuffer sb, String s, int pos) {
        if (pos == s.length()) {
            if (sb.length() == s.length() + 3) {
                result.add(sb.toString());
            }
            return;
        }

        for (int i = pos; i < s.length(); i++) {
            if (i != pos && s.charAt(pos) == '0') {
                return;
            }
            int num = Integer.parseInt(s.substring(pos, i + 1));
            if (num > 255) {
                return;
            }

            int length = sb.length();

            if (length == 0) {
                sb.append(num);
            } else {
                sb.append(".").append(num);
            }

            dfs(result, sb, s, i + 1);
            sb.setLength(length);
        }
    }
}

Palindrome Partitioning，在做dfs之前，用一个二维boolean矩阵去存从index i到index j这段s.substring(i, j + 1)是不是一个palindrome。

    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (s == null) {
            return result;
        } 

        boolean[][] isPalindrome = getIsPalindrome(s);

        List<String> list = new ArrayList<String>();
        dfs(result, list, s, isPalindrome, 0);
        return result;
    }

    private void dfs(List<List<String>> result, List<String> list, String s, boolean[][] isPalindrome, int pos) {
        if (pos == s.length()) {
            result.add(new ArrayList<String>(list));
            return;
        }

        for (int i = pos; i < s.length(); i++) {
            if (!isPalindrome[pos][i]) {
                continue;
            }
            list.add(s.substring(pos, i + 1));
            dfs(result, list, s, isPalindrome, i + 1);
            list.remove(list.size() - 1);
        }
    }

    private boolean[][] getIsPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        int m = s.length();
        boolean[][] isPalindrome = new boolean[m][m];

        for (int i = 0; i < m; i++) {
            isPalindrome[i][i] = true;
        }

        for (int i = 0; i < m - 1; i++) {
            isPalindrome[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }

        for (int distance = 2; distance < s.length(); distance++) {
            for (int i = 0; i + distance < s.length(); i++) {
                isPalindrome[i][i + distance] = isPalindrome[i + 1][i + distance - 1] && s.charAt(i) == s.charAt(i + distance);
            }
        }

        return isPalindrome;
    }
}

Letter Combinations of a Phone Number，先建存一下每个数字对应的字母

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        if (digits == null || digits.length() == 0) {
            return result;
        }

        Map<Integer, char[]> map = new HashMap<Integer, char[]>();
        map.put(0, new char[0]);
        map.put(1, new char[0]);
        map.put(2, new char[]{'a', 'b', 'c'});
        map.put(3, new char[]{'d', 'e', 'f'});
        map.put(4, new char[]{'g', 'h', 'i'});
        map.put(5, new char[]{'j', 'k', 'l'});
        map.put(6, new char[]{'m', 'n', 'o'});
        map.put(7, new char[]{'p', 'q', 'r', 's'});
        map.put(8, new char[]{'t', 'u', 'v'});
        map.put(9, new char[]{'w', 'x', 'y', 'z'});

        dfs(result, new StringBuffer(), digits, map, 0);
        return result;
    }

    private void dfs(List<String> result, StringBuffer sb, String digits, Map<Integer, char[]> map, int pos) {
        if (sb.length() == digits.length()) {
            result.add(sb.toString());
            return;
        }

        for (int i = pos; i < digits.length(); i++) {
            int num = digits.charAt(i) - '0';
            if (num < 2 || num > 9) {
                continue;
            }

            for (char c: map.get(num)) {
                sb.append(c);
                dfs(result, sb, digits, map, i + 1);
                sb.setLength(sb.length() - 1);
            }
        }
    }
}

Binary Watch

    public List<String> readBinaryWatch(int num) {
        List<String> result = new ArrayList<String>();
        int[] hours = {1, 2, 4, 8};
        int[] minutes = {1, 2, 4, 8, 16, 32};

        for (int i = 0; i <= num; i++) {
            List<Integer> hour_list = new ArrayList<Integer>();
            List<Integer> minute_list = new ArrayList<Integer>();

            dfs(hour_list, hours, i, 0, 0);
            dfs(minute_list, minutes, num - i, 0, 0);

            for (int h: hour_list) {
                for (int m: minute_list) {
                    String minute = m < 10 ? "0" + m : "" + m;
                    String time = h + ":" + minute;
                    result.add(time);
                }
            }
        }

        return result;
    }

    private void dfs(List<Integer> list, int[] array, int n, int pos, int sum) {
        if (n == 0) {
            if (array.length == 4 && sum <= 11) {
                list.add(sum);
            }
            if (array.length == 6 && sum <= 59) {
                list.add(sum);
            }
            return;
        }

        for (int i = pos; i < array.length; i++) {
            dfs(list, array, n - 1, i + 1, sum + array[i]);
        }
    }
}

解二：bit, 待做