关于一题leetcode问题

Question

老师你好。
我在做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?
        }
    }
}

Answer 1

liuyubobobo 2019-10-30 15:57:07

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

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

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

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

继续加油！：）