39. Combination Sum优化

Question

老师，这段代码可以accept，但是only faster than 5.76% ，想不到什么优化方案了，老师有没有什么建议？

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        Arrays.sort(candidates);
        boolean hasAnswer = candidates[0] <= target;
        if (!hasAnswer) {
            return result;
        }
        for (int i = 0; i < candidates.length; i++) {
            int selected = candidates[i];
            if (selected > target) {
                return result;
            }
            if (target == selected) {
                List<Integer> oneAnswer = new ArrayList<>();
                oneAnswer.add(target);
                result.add(oneAnswer);
                return result;
            } else {
                List<List<Integer>> lists = combinationSum(candidates, target - selected);
                for (List<Integer> list : lists) {
                    list.add(selected);
                    Collections.sort(list);
                    if (!result.contains(list)) {
                        result.add(list);
                    }
                }

            }

        }
        return result;
    }

Answer 1

liuyubobobo 2019-12-08 18:13:20

可以参考一下我的 Leetcode 题解代码仓的代码的思路，看看是否能看理解？

传送门：（C++ 版本） https://github.com/liuyubobobo/Play-Leetcode/blob/master/0039-Combination-Sum/cpp-0039/main.cpp

其中，最重要的递归函数，也就是发生回溯的函数，函数声明如下：

void solve(const vector<int> &candidates, 
           int index, 
           int target,    
           vector<int>& cur_res, 
           vector<vector<int>>& res)

这个函数的意思是，使用 candidates[index... n] 中的元素，凑出 target，

cur_res 存储当前找到的解；res 存储所有的解。

如果能理解这个思路，请在结合课程中的例题，仔细理解一下这类问题回溯法的过程是怎样的？

继续加油！：）

• 提问者 Ray_Lee_HZ #1

  老师，我经过思考，得到了优化方案，速度faster than 99.9%，多谢老师。