Combination Sum

Combination Sum

Given a set of candidate numbers (C) 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. Elements in
a combination (a1, a2, … , ak) must be in non-descending order. (ie,
a1 ≤ a2 ≤ … ≤ ak). 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]

思路： 把target number 传入， 每次加入一个数字，就把target number 减去这个数字递归。 当target number == 0 时，说明此时list中的数字的和为target number。 就可以将这组数字加入list里面。 注意可以重复加数字， 所以每次递归传的index就是i。

public class Solution {    public List> combinationSum(int[] candidates, int target) {        List> result = new ArrayList>();        List list = new ArrayList();        Arrays.sort(candidates);        int sum = target;        helper(result,list, sum,candidates,0);        return result;    }    private void helper(List> result, List list,int sum, int[] candidates,int index) {        if (sum == 0) {            result.add(new ArrayList(list));            return;        }        for (int i = index; i < candidates.length; i++) {            if (sum < 0) {                break;            }            list.add(candidates[i]);            helper(result,list, sum - candidates[i], candidates,i);            list.remove(list.size() - 1);        }    }}

关键字：list, sum, target

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！