39. Combination Sum优化

来源:8-5 回溯法解决组合问题的优化

Ray_Lee_HZ

2019-12-08

老师,这段代码可以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;
    }
写回答

1回答

liuyubobobo

2019-12-08

可以参考一下我的 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 存储所有的解。


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


继续加油!:)

0
1
Ray_Lee_HZ
老师,我经过思考,得到了优化方案,速度faster than 99.9%,多谢老师。
2019-12-11
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程