剑指 Offer II 082. 含有重复元素集合的组合

题目描述

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

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

注意：本题与主站 40 题相同： https://leetcode.cn/problems/combination-sum-ii/

解法

方法一

Python3JavaC++GoC#

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(u, s, t):
            if s > target:
                return
            if s == target:
                ans.append(t[:])
                return
            for i in range(u, len(candidates)):
                if i > u and candidates[i] == candidates[i - 1]:
                    continue
                t.append(candidates[i])
                dfs(i + 1, s + candidates[i], t)
                t.pop()

        ans = []
        candidates.sort()
        dfs(0, 0, [])
        return ans

class Solution {
    private List<List<Integer>> ans;
    private int[] candidates;
    private int target;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ans = new ArrayList<>();
        Arrays.sort(candidates);
        this.target = target;
        this.candidates = candidates;
        dfs(0, 0, new ArrayList<>());
        return ans;
    }

    private void dfs(int u, int s, List<Integer> t) {
        if (s > target) {
            return;
        }
        if (s == target) {
            ans.add(new ArrayList<>(t));
            return;
        }
        for (int i = u; i < candidates.length; ++i) {
            if (i > u && candidates[i] == candidates[i - 1]) {
                continue;
            }
            t.add(candidates[i]);
            dfs(i + 1, s + candidates[i], t);
            t.remove(t.size() - 1);
        }
    }
}

class Solution {
public:
    vector<int> candidates;
    vector<vector<int>> ans;
    vector<int> t;
    int target;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        this->candidates = candidates;
        this->target = target;
        vector<int> t;
        dfs(0, 0, t);
        return ans;
    }

    void dfs(int u, int s, vector<int>& t) {
        if (s > target) return;
        if (s == target) {
            ans.push_back(t);
            return;
        }
        for (int i = u; i < candidates.size(); ++i) {
            if (i > u && candidates[i] == candidates[i - 1]) continue;
            t.push_back(candidates[i]);
            dfs(i + 1, s + candidates[i], t);
            t.pop_back();
        }
    }
};

func combinationSum2(candidates []int, target int) [][]int {
    var ans [][]int
    var t []int
    sort.Ints(candidates)
    var dfs func(u, s int, t []int)
    dfs = func(u, s int, t []int) {
        if s > target {
            return
        }
        if s == target {
            ans = append(ans, slices.Clone(t))
            return
        }
        for i := u; i < len(candidates); i++ {
            if i > u && candidates[i] == candidates[i-1] {
                continue
            }
            t = append(t, candidates[i])
            dfs(i+1, s+candidates[i], t)
            t = t[:len(t)-1]
        }
    }

    dfs(0, 0, t)
    return ans
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public IList<IList<int>> CombinationSum2(int[] candidates, int target)
    {
        var dict = new SortedDictionary<int, int>(candidates.GroupBy(c => c).ToDictionary(g => g.Key, g => g.Count()));
        var paths = new List<Tuple<int, int>>[target + 1];
        paths[0] = new List<Tuple<int, int>>();
        foreach (var pair in dict)
        {
            for (var j = target; j >= 0; --j)
            {
                for (var k = 1; k <= pair.Value && j - pair.Key * k >= 0; ++k)
                {
                    if (paths[j - pair.Key * k] != null)
                    {
                        if (paths[j] == null)
                        {
                            paths[j] = new List<Tuple<int, int>>();
                        }
                        paths[j].Add(Tuple.Create(pair.Key, k));
                    }
                }
            }
        }

        var results = new List<IList<int>>();
        if (paths[target] != null) GenerateResults(results, new Stack<int>(), paths, target, paths[target].Count - 1);
        return results;
    }

    private void GenerateResults(IList<IList<int>> results, Stack<int> result, List<Tuple<int, int>>[] paths, int remaining,
        int maxIndex)
    {
        if (remaining == 0)
        {
            results.Add(new List<int>(result));
            return;
        }
        for (var i = maxIndex; i >= 0; --i)
        {
            var path = paths[remaining][i];
            for (var j = 0; j < path.Item2; ++j)
            {
                result.Push(path.Item1);
            }
            var nextMaxIndex = paths[remaining - path.Item1 * path.Item2].BinarySearch(Tuple.Create(path.Item1, int.MinValue), Comparer.Instance);
            nextMaxIndex = ~nextMaxIndex - 1;
            GenerateResults(results, result, paths, remaining - path.Item1 * path.Item2, nextMaxIndex);
            for (var j = 0; j < path.Item2; ++j)
            {
                result.Pop();
            }
        }
    }
}

class Comparer : IComparer<Tuple<int, int>>
{
    public int Compare(Tuple<int, int> x, Tuple<int, int> y)
    {
        if (x.Item1 < y.Item1) return -1;
        if (x.Item1 > y.Item1) return 1;
        return x.Item2.CompareTo(y.Item2);
    }

    public static Comparer Instance = new Comparer();
}

剑指 Offer II 082. 含有重复元素集合的组合

题目描述

解法

方法一

评论