LeetCode-216

题目

结果

代码

超时版本

class Solution {
    // Save the final answer
    private final List<List<Integer>> ans = new LinkedList<>();
    // 0 ~ 9
    private final int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Whether the num has been used
    private final boolean[] flag = new boolean[9];

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(n, k, new LinkedList<>());
        // Sort in order to deduplicate
        ans.forEach(integers -> integers.sort(Integer::compareTo));
        // Deduplicate and return the final answer
        return ans.stream().distinct().collect(Collectors.toList());
    }

    private void dfs(int target, int k, List<Integer> tmp) {
        // Time to stop recursive call
        if (k == 0 && target == 0) {
            ans.add(new LinkedList<>(tmp));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // If the num has not been used
            if (!flag[i]) {
                flag[i] = true;
                List<Integer> newTmp = new LinkedList<>(tmp);
                newTmp.add(nums[i]);
                // Recursive call
                dfs(target - nums[i], k - 1, newTmp);
                flag[i] = false;
            }
        }
    }
}

这个版本的结果，重复元素非常多，比如这个序列：

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

可以稍加改进，方法是不再考虑使用比元素更小的数，比如现在dfs到了5，那就不再考虑1~4.

优化版本

class Solution {
    // Save the final answer
    private final List<List<Integer>> ans = new LinkedList<>();
    // 0 ~ 9
    private final int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Whether the num has been used
    private final boolean[] flag = new boolean[9];

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(n, k, new LinkedList<>(), 0);
        // Sort in order to deduplicate
        ans.forEach(integers -> integers.sort(Integer::compareTo));
        // Deduplicate and return the final answer
        return ans.stream().distinct().collect(Collectors.toList());
    }

    /**
     *
     * @param target sum
     * @param k How many nums can be used
     * @param tmp From last recursive call
     * @param index Remember where to start in order to deduplicate
     */
    private void dfs(int target, int k, List<Integer> tmp, int index) {
        // Time to stop recursive call
        if (k == 0 && target == 0) {
            ans.add(new LinkedList<>(tmp));
            return;
        }

        // Start loop from index
        for (int i = index; i < nums.length; i++) {
            // If the num has not been used
            if (!flag[i]) {
                flag[i] = true;
                List<Integer> newTmp = new LinkedList<>(tmp);
                newTmp.add(nums[i]);
                // Recursive call
                dfs(target - nums[i], k - 1, newTmp, index + 1);
                flag[i] = false;
            }
        }
    }
}