Question

剑指 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/

解法

方法一

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();
}