首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

数字组合之和等于目标数

问题描述

给定一个无重复元素、且只包含正整数的int数组candidates,以及一个目标数target,然后,需要你在candidates中寻找一些数字组合起来,让它们的和等于target,你得求出所有这样的组合。注意,candidates中每个元素可以重复选取,但结果集中不能有重复的组合。例如

输入: candidates=[2,3,6], target=8

输出: [[2,2,2,2], [2,3,3], [2,6]]

问题分析

这个问题,是多步骤决策求所有解,适合用回溯法求解,回溯就会用到递归。递归当前这一层需要做的事情是,选取一个元素,加入到临时列表temp,由于每个元素都有被选取的可能,所以,外边有个for循环,穷举所有元素,但这里我们可以做个优化,初始化时,对candidates作个排序,这样当target小于当前的选取的元素时,candidates后面的元素就都不用考虑了。for循环里边,选取一个元素后,那么target-candidates[i]就作为下一层递归的target,每一层递归的最开始的几行代码,用来判断target是否等于0,等于0,意味着已经找到了该问题的一个解,可以将temp加入到result列表中,这里需要注意的是,要用

result.add (new LinkedList(temp));

相当于将当前的temp深度复制了一份,

而不能用 result.add (temp);

因为temp里边的内容是一直在变化的。

递归里边还携带了一个start参数,用于初始化for循环的i,这样可以保证每层循环都只能从后面不断选取数字,而不能选前面的,避免结果集中出现重复的组合。

代码实现

@Test

public void testCombination() {

int[] candidates = new int[]{2, 3, 4, 6};

Solution solution = new Solution();

System.out.println("result :" +

solution.generateSum(candidates, 8));

}

private class Solution {

List result = new LinkedList();

public List generateSum(

int[] candidates, int target) {

result.clear();

if (candidates == null || candidates.length == 0) {

return result;

}

Arrays.sort (candidates);

generate(candidates, 0, new LinkedList(),

target);

return result;

}

public void generate (int[] candidates, int start,

List temp, int target) {

if (target == 0) {

result.add (new LinkedList(temp));

return;

}

for (int i = start; i < candidates.length

&& candidates[i]

temp.add (candidates[i]);

System.out.println("enter: i= " + i

+", temp= "+temp+", target= "+target);

generate (candidates, i, temp,

target - candidates[i]);

temp.remove (temp.size() - 1);

System.out.println("back: i= " + i

+", temp= "+temp+", target= "+target);

}

}

}

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200407A04A7U00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券