LeetCode-40

题目

结果

代码

超时的代码

class Solution {
    private final List<List<Integer>> ans = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> candidateList = new LinkedList<>();

        // 初始化candidateList
        for (int num : candidates) {
            candidateList.add(num);
        }
        // 递归产生结果
        search(candidateList, target, new LinkedList<>());
        // 排序以便去重
        ans.forEach(integers -> integers.sort(Integer::compareTo));
        // 去重并返回
        return ans.stream().distinct().collect(Collectors.toList());
    }

    private void search(List<Integer> candidates, int target, List<Integer> tmp) {
        // 递归终止条件
        if (target < 0) {
            return;
        }
        // 找到一个合适的序列
        if (target == 0) {
            ans.add(new LinkedList<>(tmp));
        }
        for (int num : candidates) {
            List<Integer> newTmp = new LinkedList<>(tmp);
            newTmp.add(num);
            // 不能取重复的元素
            List<Integer> newCandidates = new LinkedList<>(candidates);
            newCandidates.remove((Object) num);
            // 递归
            search(newCandidates, target - num, newTmp);
        }
    }
}

上面的代码会超时，主要是因为在复制list的过程中消耗了过多的时间，可以改进一下，于是有了第二种算法。

飘过的代码

class Solution {
    private final List<List<Integer>> ans = new LinkedList<>();
    private boolean[] flag;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        flag = new boolean[candidates.length];

        List<Integer> candidateList = new LinkedList<>();
        // 初始化candidateList
        for (int num : candidates) {
            candidateList.add(num);
        }
        // 递归产生结果
        search(candidateList, target, new LinkedList<>());
        // 排序以便去重
        ans.forEach(integers -> integers.sort(Integer::compareTo));
        // 去重并返回
        return ans.stream().distinct().collect(Collectors.toList());
    }

    private void search(List<Integer> candidates, int target, List<Integer> tmp) {
        // 递归终止条件
        if (target < 0) {
            return;
        }
        // 找到一个合适的序列
        if (target == 0) {
            ans.add(new LinkedList<>(tmp));
        }

        for (int i = 0; i < candidates.size(); i++) {
            // 跳过使用过的数字
            if (flag[i]) {
                continue;
            }
            List<Integer> newTmp = new LinkedList<>(tmp);
            newTmp.add(candidates.get(i));
            // 标记
            flag[i] = true;
            // 递归
            search(candidates, target - candidates.get(i), newTmp);
            // 恢复
            flag[i] = false;
        }
    }
}