关于一题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
继续加油!:)
00
相似问题