@Yano 2015-12-30T11:25:46.000000Z 字数 14623 阅读 6893

# LeetCode之Backtracing题目汇总

LeetCode

LeetCode 题目汇总

# 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.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7
A solution set is:
[7]
[2, 2, 3]

    public List<List<Integer>> combinationSum(int[] candidates, int target) {        if (candidates == null || candidates.length == 0) {            return new ArrayList<List<Integer>>();        }        List<List<Integer>> result = new ArrayList<List<Integer>>();        ArrayList<Integer> cur = new ArrayList<Integer>();        Arrays.sort(candidates);        dfs(0, target, result, cur, candidates);        return result;    }    private void dfs(int start, int target, List<List<Integer>> result,            ArrayList<Integer> cur, int[] candidates) {        if (target == 0) {            result.add(new ArrayList<Integer>(cur));            return;        }        for (int i = start; i < candidates.length; i++) {            // candidates[i] > target，则递归结束，后面不可能是解            if (candidates[i] > target) {                return;            }            cur.add(candidates[i]);            dfs(i, target - candidates[i], result, cur, candidates);            cur.remove(cur.size() - 1);        }    }

# Combination Sum II

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

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

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

1. Combination Sum每个元素可以使用多次，所以递归是dfs(i, target - candidates[i], result, cur, candidates);
2. Combination Sum II每个元素只能使用一次，所以递归是dfs(i + 1, target - candidates[i], rt, cur, candidates);因为解可能重复，所以使用set，最后转成list。
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {        if (candidates == null || candidates.length == 0) {            return new ArrayList<List<Integer>>();        }        Set<List<Integer>> rt = new HashSet<List<Integer>>();        ArrayList<Integer> cur = new ArrayList<Integer>();        Arrays.sort(candidates);        dfs(0, target, rt, cur, candidates);        return new ArrayList<List<Integer>>(rt);    }    private void dfs(int start, int target, Set<List<Integer>> rt,            ArrayList<Integer> cur, int[] candidates) {        if (target == 0) {            rt.add(new ArrayList<Integer>(cur));            return;        }        for (int i = start; i < candidates.length; i++) {            // candidates[i] > target，则递归结束，后面不可能是解            if (candidates[i] > target) {                return;            }            cur.add(candidates[i]);            dfs(i + 1, target - candidates[i], rt, cur, candidates);            cur.remove(cur.size() - 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.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

    public List<List<Integer>> combinationSum3(int k, int n) {        List<List<Integer>> rt = new ArrayList<List<Integer>>();        if (k < 1 || n < 1) {            return rt;        }        List<Integer> cur = new ArrayList<Integer>();        dfs(rt, cur, 0, k, n, 1);        return rt;    }    private void dfs(List<List<Integer>> rt, List<Integer> cur, int sum, int k,            int n, int level) {        if (sum == n && k == 0) {            rt.add(new ArrayList<Integer>(cur));            return;        } else if (sum > n || k <= 0) {            return;        }        for (int i = level; i <= 9; i++) {            cur.add(i);            dfs(rt, cur, sum + i, k - 1, n, i + 1);            cur.remove(cur.size() - 1);        }    }

# Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]


    int target;// 次数    Integer[] stack;// 存储每次排列    Integer[] nums;// 存储1~n    List<List<Integer>> rt;// 存储结果    public void search(int p) {        // 若长度为k，则stack是其中一个结果，保存结果        if (p == target) {            rt.add(new ArrayList<Integer>(Arrays.asList(stack)));            return;        }        // 对于nums(1~n)中的每个元素        for (Integer n : nums) {            // 找到nums中第一个比stack最后元素大的元素            if (p > 0 && n <= stack[p - 1]) {                continue;            }            // 找到下一个元素，递归            stack[p] = n;            search(p + 1);        }    }    public List<List<Integer>> combine(int n, int k) {        target = k;        nums = new Integer[n];        stack = new Integer[k];        for (int i = 0; i < nums.length; i++) {            nums[i] = i + 1;        }        rt = new ArrayList<List<Integer>>();        search(0);        return rt;    }

# Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

    public List<String> generateParenthesis(int n) {        if (n <= 0) {            return new ArrayList<String>();        }        ArrayList<String> rt = new ArrayList<String>();        dfs(rt, "", n, n);        return rt;    }    void dfs(ArrayList<String> rt, String s, int left, int right) {        if (left > right) {            return;        }        if (left == 0 && right == 0) {            rt.add(s);        }        if (left > 0) {            dfs(rt, s + "(", left - 1, right);        }        if (right > 0) {            dfs(rt, s + ")", left, right - 1);        }    }

# Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2


Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

    public List<Integer> grayCode(int n) {        List<Integer> rt = new ArrayList<Integer>();        if (n < 0) {            return rt;        }        for (int i = 0; i < Math.pow(2, n); i++) {            rt.add((i >> 1) ^ i);        }        return rt;    }

# Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input: Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

    static final char[][] CHAR_MAP = { {},// 0            {},// 1            { 'a', 'b', 'c' },// 2            { 'd', 'e', 'f' },// 3            { 'g', 'h', 'i' },// 4            { 'j', 'k', 'l' },// 5            { 'm', 'n', 'o' },// 6            { 'p', 'q', 'r', 's' },// 7            { 't', 'u', 'v' },// 8            { 'w', 'x', 'y', 'z' } // 9    };    List<String> result;    char[] stack;    public List<String> letterCombinations(String digits) {        if (digits == null || digits.length() == 0) {            return new ArrayList<String>();        }        result = new ArrayList<String>();        stack = new char[digits.length()];        dfs(digits.toCharArray(), 0);        return result;    }    private void dfs(char[] digits, int p) {        if (p == digits.length) {            result.add(new String(stack));        } else {            int num = digits[p] - '0';            for (char c : CHAR_MAP[num]) {                stack[p] = c;                dfs(digits, p + 1);            }        }    }

# Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
["aa","b"],
["a","a","b"]
]


    public List<List<String>> partition(String s) {        List<List<String>> rt = new ArrayList<List<String>>();        if ("".equals(s)) {            return rt;        }        if (s.length() == 1) {            rt.add(Arrays.asList(s));            return rt;        }        for (int i = 0; i < s.length(); i++) {            String x = s.substring(0, i + 1);            List<List<String>> sub = new ArrayList<List<String>>();            if (isPal(x)) {                sub = partition(s.substring(i + 1));                if (sub.isEmpty()) {                    rt.add(Arrays.asList(x));                } else {                    for (List<String> l : sub) {                        List<String> _l = new ArrayList<String>();                        _l.add(x);                        _l.addAll(l);                        rt.add(_l);                    }                }            }        }        return rt;    }    static boolean isPal(String s) {        int st = 0, ed = s.length() - 1;        while (st < ed) {            if (s.charAt(st++) != s.charAt(ed--)) {                return false;            }        }        return true;    }

# Permutation Sequence

The set [1,2,3,…,_n_] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

k1/(n−1)!

k1=k

k2/(n−2)!

k2=k1

    public String getPermutation(int n, int k) {        if (n <= 0 || k <= 0) {            return "";        }        String rt = "";        List<Integer> list = new ArrayList<Integer>();        int fact = 1;        for (int i = 1; i <= n; i++) {            list.add(i);            fact *= i;        }        k--;        for (int i = 0; i < n; i++) {            fact /= (n - i);            int index = k / fact;            rt += list.get(index);            list.remove(index);            k %= fact;        }        return rt;    }

# Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2], and [3,2,1].

    public List<List<Integer>> permute(int[] nums) {        if (nums == null || nums.length == 0) {            return new ArrayList<List<Integer>>();        }        ArrayList<List<Integer>> rt = new ArrayList<List<Integer>>();        if (nums.length == 1) {            rt.add(new ArrayList<Integer>(Arrays.asList(nums[0])));        } else {            for (int i = 0; i < nums.length; i++) {                for (List<Integer> l : permute(resetof(nums, i))) {                    l.add(nums[i]);                    rt.add(l);                }            }        }        return rt;    }    private int[] resetof(int[] nums, int index) {        int[] rt = new int[nums.length - 1];        int s = 0;        for (int i = 0; i < nums.length; i++) {            if (i != index) {                rt[s++] = nums[i];            }        }        return rt;    }

# Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2][1,2,1], and [2,1,1].

    void swap(int x[], int a, int b) {        int t = x[a];        x[a] = x[b];        x[b] = t;    }    public boolean nextPermutation(int[] num) {        if (num.length < 2)            return false;        int p = -1;        for (int i = num.length - 1; i > 0; i--) {            if (num[i] > num[i - 1]) {                p = i - 1;                break;            }        }        if (p == -1) {            Arrays.sort(num);            return false;        }        int c = -1;        for (int i = num.length - 1; i >= 0; i--) {            if (num[i] > num[p]) {                c = i;                break;            }        }        swap(num, p, c);        Arrays.sort(num, p + 1, num.length);        return true;    }    List<Integer> asList(int[] num) {        ArrayList<Integer> l = new ArrayList<Integer>(num.length);        for (int i = 0; i < num.length; i++)            l.add(num[i]);        return l;    }    public List<List<Integer>> permuteUnique(int[] num) {        Arrays.sort(num);        ArrayList<List<Integer>> found = new ArrayList<List<Integer>>();        found.add(asList(num));        while (nextPermutation(num)) {            found.add(asList(num));        }        return found;    }

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

    List<String> rt = new ArrayList<String>();    String[] stack = new String[4];    public List<String> restoreIpAddresses(String s) {        if (s == null || s.length() == 0) {            return new ArrayList<String>();        }        dfs(s, 0, 0);        return rt;    }    /**     *      * @param s     * @param p     *            :指针     * @param pstack     *            :stack的下标     */    public void dfs(String s, int p, int pstack) {        if (pstack == 4) {            // 如果stack长度为4，且s的字符全部用上            // 则stack[0...3]存了一个结果            if (p >= s.length()) {                String ip = String.join(".", stack);                rt.add(ip);            }            return;        }        // 获取1~3个字符        for (int i = 1; i <= 3; i++) {            // 如果超过字符串长度，返回            if (p + i > s.length()) {                return;            }            // 若选取的第一个字符是0，则停止选取            if (i > 1 && s.charAt(p) == '0') {                continue;            }            String number = s.substring(p, p + i);            // 如果number<=255，递归            if (Integer.parseInt(number) <= 255) {                stack[pstack] = number;                dfs(s, p + i, pstack + 1);            }        }    }

# Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]

    int target;// 次数    Integer[] stack;// 存储每次排列    List<List<Integer>> rt;// 存储结果    public void search(int p, int[] nums) {        // 若长度为k，则stack是其中一个结果，保存结果        if (p == target) {            rt.add(new ArrayList<Integer>(Arrays.asList(stack)));            return;        }        for (int i = 0; i < nums.length; i++) {            if (p > 0 && nums[i] <= stack[p - 1]) {                continue;            }            stack[p] = nums[i];            search(p + 1, nums);        }    }    public List<List<Integer>> subsets(int[] nums) {        Arrays.sort(nums);        rt = new ArrayList<List<Integer>>();        // 分别做0~num.length长度的组合        for (int i = 0; i <= nums.length; i++) {            target = i;            stack = new Integer[i];            search(0, nums);        }        return rt;    }

# Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[  [2],  [1],  [1,2,2],  [2,2],  [1,2],  []]

    public List<List<Integer>> subsetsWithDup(int[] nums) {        if (nums == null) {            return null;        }        if (nums.length == 0) {            return new ArrayList<List<Integer>>();        }        Set<List<Integer>> set = new HashSet<List<Integer>>();        // 题目中要求每个list是非降序，所以要先从小到大排序        Arrays.sort(nums);        // 对于n位，有2^n种情况        for (int i = 0; i < Math.pow(2, nums.length); i++) {            List<Integer> list = new ArrayList<Integer>();            int tmp = i;            // 对于每种情况，分别求得二进制中1的个数            // 0代表不选择，1代表选择            for (int j = 0; j < nums.length; j++) {                int bit = tmp & 1;                tmp >>= 1;                if (bit == 1) {                    list.add(nums[j]);                }            }            set.add(list);        }        return new ArrayList<List<Integer>>(set);    }

# Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]


word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

    public boolean exist(char[][] board, String word) {        if (board == null || board[0].length == 0 || board.length == 0                || word == null) {            return false;        }        int rows = board.length;        int cols = board[0].length;        boolean[] visited = new boolean[rows * cols];        int pathLength = 0;        for (int row = 0; row < rows; row++) {            for (int col = 0; col < cols; col++) {                // 以row,col为开始，能够遍历得到结果                if (dfs(board, rows, cols, row, col, word, pathLength, visited)) {                    return true;                }            }        }        return false;    }    public boolean dfs(char[][] board, int rows, int cols, int row, int col,            String word, int pathLength, boolean[] visited) {        // 如果pathLength的长度已经是查找字串的长度，则已经找到        if (pathLength == word.length()) {            return true;        }        boolean hasPath = false;        // 符合条件的情况下：        // 1. 行、列均在矩阵范围内        // 2. board[row][col]是所要找的字符        // 3. board[row][col]没有遍历过        if (row >= 0 && row < rows && col >= 0 && col < cols                && board[row][col] == word.charAt(pathLength)                && !visited[row * cols + col]) {            pathLength++;            visited[row * cols + col] = true;            hasPath = dfs(board, rows, cols, row, col - 1, word, pathLength,                    visited)                    || dfs(board, rows, cols, row - 1, col, word, pathLength,                            visited)                    || dfs(board, rows, cols, row, col + 1, word, pathLength,                            visited)                    || dfs(board, rows, cols, row + 1, col, word, pathLength,                            visited);            // 若board[row][col]的前后左右没有满足条件的字符，则回退            if (!hasPath) {                pathLength--;                visited[row * cols + col] = false;            }        }        return hasPath;    }

• 私有
• 公开
• 删除