【Day 80 】2024-06-26 - 39 组合总和

[azl397985856]

39 组合总和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/combination-sum/

前置知识

• 剪枝
• 回溯

  题目描述

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

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

说明：

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

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

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

提示：

1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都是独一无二的。 1 <= target <= 500

[Lizhao-Liu]

func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
    var result = [[Int]]()
    var combination = [Int]()

    func backtrack(_ start: Int, _ target: Int) {
        if target == 0 {
            result.append(combination)
            return
        }
        if target < 0 {
            return
        }
        for i in start..<candidates.count {
            combination.append(candidates[i])
            backtrack(i, target - candidates[i])
            combination.removeLast()
        }
    }

    backtrack(0, target)
    return result
}

[zhiyuanpeng]

class Solution:
    def combinationSum(
        self, candidates: List[int], target: int
    ) -> List[List[int]]:

        results = []

        def backtrack(remain, comb, start):
            if remain == 0:
                # make a deep copy of the current combination
                results.append(list(comb))
                return
            elif remain < 0:
                # exceed the scope, stop exploration.
                return

            for i in range(start, len(candidates)):
                # add the number into the combination
                comb.append(candidates[i])
                # give the current number another chance, rather than moving on
                backtrack(remain - candidates[i], comb, i)
                # backtrack, remove the number from the combination
                comb.pop()

        backtrack(target, [], 0)

        return results

[Dtjk]

class Solution { Set<List> ans = new HashSet<>(); public List<List> combinationSum(int[] candidates, int target) { int n = candidates.length; dfs(candidates,target,0,new ArrayList<>()); List<List> res = new ArrayList<>(); res.addAll(ans); return res; } void dfs(int[] nums,int target,int num,List l){ if (num > target){ return; } if (num == target){ List tmp = new ArrayList<>(l); Collections.sort(tmp); ans.add(tmp); } int n = nums.length; for (int i = 0;i < n;i++){ l.add(nums[i]); dfs(nums,target,num + nums[i],l); l.remove(l.size() - 1); } } }