【LeetCode】39. Combination Sum

问题描述

https://leetcode.com/problems/combination-sum/#/description

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]
]

问题分析

求一列数中可以相加起来等于目标数的所有组合，并且数组中的数可以重复使用。

代码

Github上LeetCode代码：https://github.com/zgljl2012/leetcode-java

public class Solution {
	    public List<List<Integer>> combinationSum(int[] candidates, int target) {
	    	List<List<Integer>> result = new ArrayList<>();
	    	if(candidates ==null || candidates.length == 0) {
	    		return result;
	    	}
	    	Arrays.sort(candidates);
	    	fun(result, new ArrayList<>(), 0, target, candidates);
	    	return result;
	    }
	    
	    /**
	     * @param result 结果集
	     * @param list 当前的结果数组
	     * @param cur 已经遍历到的数组指针
	     * @param target 目标数
	     */
	    public void fun(List<List<Integer>> result, List<Integer> list, int cur, int target, int[] candidates) {
	    	if(target > 0) {
	    		for(int i = cur; i < candidates.length && target >= candidates[i]; i++) {
	    			list.add(candidates[i]); // 将当前数加入到数组中
	    			fun(result, list, i, target - candidates[i], candidates);
	    			list.remove(list.size()-1);// 因为到这儿递归的一轮就结束了，最后一个数已被判断了，所以需要移除
	    		}
	    	} else if(target == 0) {
	    		result.add(new ArrayList<>(list));
	    	}
	    }
	    
	    
	}