今天和大家聊的问题叫做 组合总和,我们先来看题面:
https://leetcode-cn.com/problems/combination-sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
题意
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明:所有数字(包括 target)都是正整数。解集不能包含重复的组合。
样例
示例 1: 输入:candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入:candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
题解
回溯法
回溯算法关键在于:不合适就退回上一步,然后通过约束条件, 减少时间复杂度.
假设candidates = [2, 3, 6, 7],target = 7
以 target = 7 为根结点,每一个分支做减法。减到 0 或者负数的时候,剪枝。其中,减到 0 的时候结算,这里 “结算” 的意思是添加到结果集。
代码如下:
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(candidates); backtrack(candidates, target, res, 0, new ArrayList<Integer>()); return res; } private void backtrack(int[] candidates, int target, List<List<Integer>> res, int i, ArrayList<Integer> tmp_list) { if (target < 0) return; if (target == 0) { res.add(new ArrayList<>(tmp_list)); return; } for (int start = i; start < candidates.length; start++) { if (target < candidates[start]) break; tmp_list.add(candidates[start]); backtrack(candidates, target - candidates[start], res, start, tmp_list); tmp_list.remove(tmp_list.size() - 1); } } }
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。