代码编织梦想

LeetCode第39题-组合总和-java实现-图解思路与手撕代码


一、题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

二、解题思路与代码实现

1.解题思路

这道题适合用回溯的方法解决,每次递归需要考虑两种情况,选择这个数字,和不选这个数字。

如果选择这个数字,target减去这个数字,然后进行传递。

如果不选这个数字,下一次传递时考虑数组中下一个数字。

每次传递需要考虑target是否小于等于零,数组是否遍历结束。

如果target等于零,则保存当前组合,其他情况结束当前传递,直接return。

2.代码实现

代码如下(示例):

    private static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new LinkedList<>();
        dfs(0, target, candidates, res, new LinkedList<Integer>());
        return res;
    }

    private static void dfs(int idx, int target, int[] candidates, List<List<Integer>> res, LinkedList<Integer> temp) {
        if (target==0){
            res.add(new LinkedList<Integer>(temp));
            return;
        }
        if (idx==candidates.length || target<0){
            return;
        }
        dfs(idx+1, target, candidates, res, temp);
        temp.add(candidates[idx]);
        dfs(idx, target-candidates[idx], candidates, res, temp);
        temp.removeLast();
    }

其中需要注意的是new LinkedList(temp)的用法,还有,temp.pop()不是去掉最后加入的数字,而是去掉当前链表中最先加入的数字。


总结

这道题看上去很复杂,需要考虑很多情况,但是最后结局思路却很简单,只需考虑选和不选两个情况,是一道经典的回溯问题。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45271005/article/details/127972791

leetcode第3题无重复字符的最长子串-java实现-图解思路与手撕代码-滑动窗口_在下柠檬的博客-爱代码爱编程

LeetCode第3题无重复字符的最长子串-java实现-图解思路与手撕代码-滑动窗口 文章目录 一、题目描述二、解题思路与代码实现1.思路2.滑动窗口的代码 总结 一、题目描述 给定一个

leetcode第9题-回文数-java实现-图解思路与手撕代码_在下柠檬的博客-爱代码爱编程

LeetCode第9题-回文数-java实现-图解思路与手撕代码 文章目录 一、题目描述二、解题思路与代码实现1.解题思路2.代码实现 总结 一、题目描述 给你一个整数 x ,如果 x 是

leetcode第15题-三数之和-java实现-图解思路与手撕代码_在下柠檬的博客-爱代码爱编程

LeetCode第15题-三数之和-java实现-图解思路与手撕代码 文章目录 一、题目描述二、解题思路与代码实现1.解题思路2.相加部分实现 总结 一、题目描述 给你一个整数数组 num

leetcode第29题-两数相除-java实现-图解思路与手撕代码_在下柠檬的博客-爱代码爱编程

LeetCode第29题-两数相除-java实现-图解思路与手撕代码 文章目录 一、题目描述二、解题思路与代码实现1.解题思路2.相加部分实现 总结 一、题目描述 给定两个整数,被除数 d

leetcode第32题-爱代码爱编程

LeetCode第32题-最长有效括号-java实现-图解思路与手撕代码 文章目录 一、题目描述二、解题思路与代码实现1.解题思路2.代码实现 总结 一、题目描述 给你一个只包