题目描述

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

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

说明：

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

样例

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

算法分析

dfs

• 1、暴力枚举每个数字选多少个
• 2、当枚举到的总值sum > target，表示该枚举方式不合法，直接return
• 3、当枚举完每个数字之后，若sum == target，表示该选择方案是合法的，记录该方案

注意:枚举的时候的小细节，枚举每个数字选多少个的时候，本来是枚举多少个，最后dfs下一层完后，就应该全部恢复现场，删除多少个，再枚举下一种情况。可以直接枚举该数字选多少个，假设最多能选t个，则每选一个dfs一次，操作了t + 1次之后，再把这t个相同的数字一次性恢复现场 (y总的小技巧)

时间复杂度

不好分析

Java 代码

class Solution {
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    static void dfs(int[] candidates,int target,int u,int sum,List<Integer> t)
    {
        if(sum > target) return ;

        if(u == candidates.length)
        {
            if(sum == target)
            {
                ans.add(new ArrayList<Integer>(t));
            }
            return;
        }
        //枚举每个数字用多少次
        for(int i = 0;sum + candidates[u] * i <= target;i ++)
        {
            dfs(candidates,target,u + 1,sum + candidates[u] * i,t);
            t.add(candidates[u]);
        }

        for(int i = 0;sum + candidates[u] * i <= target;i ++)
            t.remove(t.size() - 1);
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ans.clear();
        List<Integer> t = new ArrayList<Integer>();
        dfs(candidates,target,0,0,t);

        return ans;
    }
}