代码随想录算法训练营第二十五天

LeetCode 216.组合总和-iii

注意可以剪枝，后续再研究.

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> path = new LinkedList<>();
        backtracking(res, path, k, n, 1);
        return res;
    }

    private void backtracking (List<List<Integer>> res, List<Integer> path, int k, int n, int index) {

        // recursion exits if size == k && sum == n
        if (path.size() == k && getSum(path) == n) {
            List<Integer> combo = new LinkedList<>();
            combo.addAll(path);
            res.add(combo);
        }

        // traverse the [index, 9]
        for (int i = index; i < 10; i++) {
            // add this value into path
            path.add(i);

            // traverse the right side numbers
            backtracking(res, path, k, n, i + 1);

            // backtrack here
            path.remove(path.get(path.size() - 1));
        }

    }

    // a helper method
    private int getSum ( List<Integer> list) {
        int sum = 0;
        for (Integer integer : list) {
            sum += integer;
        }
        return sum;
    }
}

LeetCode 17.电话号码的字母组合

还有一些小的优化可以做，比如可以把hashmap换成数组。

class Solution {
    public List<String> letterCombinations(String digits) {
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        List<String> ans = new LinkedList<>();
        List<Character> path = new LinkedList<>();

        if (digits.length() > 0) {
            backtracking(map, ans, path, digits);
        }

        return ans;

    }

    private void backtracking (Map<Character, String> map, List<String> ans, List<Character> path, String digits) {

        // recursion exits if the length approach its target
        if (path.size() == digits.length()) {

            StringBuffer sb = new StringBuffer();

            for (Character character : path) {
                sb.append(character);
            }

            ans.add(new String(sb));
            return;
        }

        char digit = digits.charAt(path.size());
        String str = map.get(digit);

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            path.add(c);

            backtracking(map, ans, path, digits);

            // false way
            // path.remove(path.get(path.size() - 1));

            // correct one
            path.remove(path.size() - 1);
        }

    }
}