leetcode39 combination sum

luoyibu 发布于2019-08-16 10:33 / 3364人阅读

摘要：在这道题中，我结合了递归的思想来。就是将当前的值作为一个潜在的结果值加入一个结果数组将数组作为当前结果传入下一轮递归。

题目要求

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 
[
  [7],
  [2, 2, 3]
]

一个整数数组，数组中的值不重复，要求在数组中找到所有的子数组，子数组满足元素的和为目标值的条件

思路和代码

这道题目有一个标签是backtracking，即在前一种条件的情况下计算当前条件产生的结果值。在这道题中，我结合了递归的思想来。就是将当前的值作为一个潜在的结果值加入一个结果数组将数组作为当前结果传入下一轮递归。

public class CombinationSum_39 {
    List> result = new ArrayList>();
    public List> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        
        for(int i = 0 ; i temp = new ArrayList();
                temp.add(candidates[i]);
                combinationSum(candidates, i, target-candidates[i], temp);

            }
        }
        return result;
    }
    
    public void combinationSum(int[] candidates, int start, int target, List currentResult){
        for(int i = start ; i < candidates.length ; i++){
            if(candidates[i] == target){
                currentResult.add(candidates[i]);
                result.add(currentResult);
                return;
            }
            if(candidates[i] > target){
                return;
            }
            if(candidates[i] < target){
                List temp = new ArrayList();
                temp.addAll(currentResult);
                temp.add(candidates[i]);
                combinationSum(candidates, i, target-candidates[i], temp);
            }
        }
    }
}

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器服务器托管 Leetcod LeetCode Combining Combinations

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70006.html

leetcode-39-Combination Sum

摘要：分为每次从里边循环所有数，已有值减去所有数，新值作为已有值，继续处理。遇到返回保存，负数去掉 39. Combination SumDescriptionHintsSubmissionsDiscussSolutionGiven a set of candidate numbers (C) (without duplicates) and a target number (T),find...

Drummor 2019-07-30 15:43 评论0 收藏0
leetcode40 combination sum 2

摘要：参考思路和非常类似，只是这里需要增加进行重复处理的部分。题目要求题目中新添的要求包括数组中存在重复值，而且数组中每个值只可以使用一次。需要注意的是，既然数组中存在重复的值，就要注意可能会将重复的情况加入结果数组。参考思路和leetcode39 combination sum 非常类似，只是这里需要增加进行重复处理的部分。请参考我对leetcode39进行解答的这篇博客。题目要求 ...

Code4App 2019-08-16 10:33 评论0 收藏0
LeetCode偶尔一题 —— 39. Combination Sum（回溯算法系列）

摘要：输入输出分析题目由于我们需要找到多个组合，简单的使用循环肯定是不行的，这时候我们可以使用回溯算法来解决这个问题。用回溯算法解决问题的一般步骤针对所给问题，定义问题的解空间，它至少包含问题的一个最优解。题目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...

linkin 2019-08-23 18:29 评论0 收藏0
leetcode 40 Combination Sum II

摘要：要求中的每一个元素在一个组合中只能被使用一次。输入候选数字集和目标数字结果集应当是想法首先这道题和题非常的相像。因此和题的解法相比，我们需要进行一次对于重复元素跳过的操作。题目详情 Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C...

li21 2019-08-15 14:18 评论0 收藏0
Leetcode 相似题只有题号不含代码。

找出string里的单词。 186. Reverse Words in a String II, 434. Number of Segments in a String combination类型题 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

StonePanda 2019-08-14 18:01 评论0 收藏0