JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40

Code

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        helper(candidates, res, target, new ArrayList<Integer>(), 0);
        return res;
    }

    private void helper(int[] nums, List<List<Integer>> res, int target, List<Integer> temp, int start){
        if(target < 0) return;
        if(target == 0){
            res.add(new ArrayList<>(temp));
            return;
        }

        for(int i = start; i < nums.length; i++){
            temp.add(nums[i]);
            helper(nums, res, target - nums[i], temp, i);
            temp.remove(temp.size() - 1);
        }
    }
}

N 是 candidates 的数量, T 是 target, M 是 candidates 中的最小值.

时间复杂度 O(N^(T/M + 1))

  • 每一个节点的处理时间是 constant, 那么有多少个节点要处理就是时间复杂度.
  • 每个节点会生成 N 个子节点，树的最大深度是 T/M
  • N 树的节点个数是 N^(T/M + 1) - 深度+1

空间复杂度 O(T/M)

  • 假设每次都添加最小元素 M, 那么最大深度就是 T/M
  • 这个空间复杂度计算并没有考虑结果(result)的个数