求和为给定值的组合

求和为给定值的组合

问题

这个题目说的是，给你一个正整数数组，数组中不包含重复元素，同时给你一个正整数目标值，你要找到数组中和为目标值的所有组合。另外，数组中每个元素都可以使用无限多次，并且答案中不能包含重复组合。

比如说，给你的数组是：

4, 2, 8

给你的目标值是 6。数组中和为 6 的组合有：

[4, 2]
[2, 2, 2]

代码

public class AlgoCasts {

  private void combSum(int[] nums, int target, int start,
                       List<Integer> elem, List<List<Integer>> result) {
    if (target == 0) {
      result.add(new ArrayList<>(elem));
      return;
    }
    if (target < 0) return;
    for (int i = start; i < nums.length; ++i) {
      elem.add(nums[i]);
      combSum(nums, target-nums[i], i, elem, result);
      elem.remove(elem.size()-1); // T: O(1)
    }
  }

  // Time: O(n^(target/min)), Space: O(target/min)
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> elem = new ArrayList<>();
    combSum(candidates, target, 0, elem, result);
    return result;
  }

  private void combSumSort(int[] nums, int target, int start,
                           List<Integer> elem, List<List<Integer>> result) {
    if (target == 0) {
      result.add(new ArrayList<>(elem));
      return;
    }
    if (target < 0) return;
    for (int i = start; i < nums.length; ++i) {
      if (nums[i] > target) break;
      elem.add(nums[i]);
      combSumSort(nums, target-nums[i], i, elem, result);
      elem.remove(elem.size()-1); // T: O(1)
    }
  }

  // Time: O(n^(target/min)), Space: O(target/min)
  public List<List<Integer>> combinationSumSort(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> elem = new ArrayList<>();
    Arrays.sort(candidates);
    combSumSort(candidates, target, 0, elem, result);
    return result;
  }

}