一、题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。

点击查看原题
难度级别： 中等

二、思路

1）回溯法

由于同一数字可以被无限制重复选取，求和不需要管顺序，那么可以使用从前往后遍历数组的办法，每遍历一个数就是更深一层的搜索，记录遍历路径和遍历路径值的总和，将该题看作多叉树的深度搜索

三、代码

1）回溯法

  1. class Solution {
  2.     List<List<Integer>> ans;
  3.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  4.         ans = new ArrayList();
  5.         List<Integer> temp = new ArrayList();
  6.         dfs(candidates, target, temp, 0, 0);
  7.         return ans;
  8.     }
  9.     private void dfs(int[] candidates, int target, List<Integer> temp, int loc, int val) {
  10.         if (val > target) {
  11.             return;
  12.         }
  13.         if (target == val) {
  14.             ans.add(new ArrayList<Integer>(temp));
  15.             return ;
  16.         }
  17.         for (int i = loc; i < candidates.length; i++) {
  18.             temp.add(candidates[i]);
  19.             dfs(candidates, target, temp, i, val + candidates[i]);
  20.             temp.remove(temp.size()-1);
  21.         }
  22.     }
  23. }

s为所有可行解长度之和，时间复杂度为O(s)，空间复杂度为O(target)