Posted Updated LeetCode / Mediuma minute read (About 189 words)

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

回溯，每个回溯层级添加数字对应的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<String> letterCombinations(String digits) {

        
        List<String> ret = new ArrayList<>();
        if(digits.equals("")) return ret;
        
        char[][] bin = new char[8][0];
        bin[0] = new char[]{'a', 'b', 'c'}; 
        bin[1] = new char[]{'d', 'e', 'f'};
        bin[2] = new char[]{'g', 'h', 'i'};
        bin[3] = new char[]{'j', 'k', 'l'};
        bin[4] = new char[]{'m', 'n', 'o'};
        bin[5] = new char[]{'p', 'q', 'r', 's'};
        bin[6] = new char[]{'t', 'u', 'v'};
        bin[7] = new char[]{'w', 'x', 'y', 'z'};
        
        backtracking(ret, new StringBuffer(), bin, digits, 0);
        return ret;
    }
    
    private void backtracking(List<String> ret, StringBuffer sb, char[][] bin, String digits, int i){
        if(sb.length() == digits.length() ){
            ret.add(sb.toString());
            return;
        }
        
        for(char c : bin[digits.charAt(i)-'2']){
            sb.append(c);
            backtracking(ret, sb, bin, digits, i+1);
            sb.delete(sb.length()-1, sb.length());
        }
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 229 words)

40. Combination Sum II

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

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

Note: The solution set must not contain duplicate combinations.

由于有重复性元素，因此先将数组排序。
储存一个数组，记录元素是否被选择。
回溯，遍历选择元素，并计算加和，并记录选择的元素。当选择的元素与上一个元素重复时，则跳过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates, ret, new ArrayList<>(), new int[candidates.length], target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int[] visited, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            if(i > 0 && candidates[i] == candidates[i-1] && visited[i-1] == 0) continue;
            visited[i] = 1;
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, visited, target, sum, i+1);
            visited[i] = 0;
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 240 words)

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

回溯，记录当前加和。
遍历所有数组元素，当sum大于target时返回，等于target时加入数组并返回。
每次遍历并回溯元素时只递归当前元素和其之后的元素。（防止重复。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        backtracking(candidates, ret, new ArrayList<>(), target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, target, sum, i);
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 228 words)

77. Combinations

问题
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

回溯，构建搜索树。
子节点取出的数值应大于父节点中取出的数值。
直到树高度达到k后返回。

返回时，要new一个List，将原有list传入。
否则添加到ans的值只是list的内存地址。
ArrayList换成LinkedList可以优化一些速度，因为可以直接removeLast。（22ms -> 16ms）
i的范围限制在start到n-k+1，后面的限制容易被忽略，可以大幅度减枝，优化速度。（16ms -> 1ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<>();
        backTrack(new LinkedList(),1,n,k);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list, int start, int n, int k){
        if (k == 0){
            ans.add(new ArrayList(list));
            return;
        }

        for (int i = start; i <= n-k+1; i++){
            list.add(i);
            backTrack(list, i+1, n, k-1);
            list.removeLast();
        }
    }
}
Follow

Recents

Archives

Links

×