关于一题leetcode问题

来源:3-3 DFS逻辑的微观解读

慕仔2475814

2019-10-30

老师你好。
我在做leetcode第377题时,想用dfs解决,但是怎么想backtrack的时候got stuck不知道咋做了,老师能帮看下么?
https://leetcode.com/problems/combination-sum-iv

class Solution {
    private int count;
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        this.count = 0;
        _find(nums, target, 0);
        return count;
    }
    private void _find(int[] nums, int target, int start) {
        if (target == 0) {
            count++;
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if(nums[i] > target) {
                break;
            }
            _find(nums, target - nums[i], i);
            //how to backtrack?
        }
    }
}
写回答

1回答

liuyubobobo

2019-10-30

抱歉,你需要告诉我,你 stuck 在了什么地方,具体哪里想不明白?或者你的想法是怎样的,你觉得根据你的想法,结果应该是怎样的,可实际却是怎样的?你为什么不能理解实际上的运行结果?


你这样扔给我有一个代码,我也不知道要回答你什么问题。我只能说,377 号问题,我的参考代码如下:https://github.com/liuyubobobo/Play-Leetcode/tree/master/0377-Combination-Sum-IV/cpp-0377


其中第一个代码是记忆化搜索,在递归的基础上加上记忆化。


关于记忆化搜索的详细讲解,可以参考我的课程《玩转算法面试》:https://coding.imooc.com/class/82.html


继续加油!:)

0
0

玩转算法系列--图论精讲(Java版)

30+小时系统学习,bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

查看课程