【Leecode】Leecode刷题之路第40天之组合总和II

2025/5/7 3:45:08 来源：https://blog.csdn.net/Prince140678/article/details/143474723 浏览: 次关键词：【Leecode】Leecode刷题之路第40天之组合总和II

题目出处

40-组合总和II-题目出处

题目描述

在这里插入图片描述

个人解法

思路：

todo

代码示例：（Java）

todo

复杂度分析

todo

官方解法

40-组合总和II-官方解法

方法1：回溯

思路：

在这里插入图片描述

代码示例：（Java）

public class Solution1 {List<int[]> freq = new ArrayList<int[]>();List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> sequence = new ArrayList<Integer>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);for (int num : candidates) {int size = freq.size();if (freq.isEmpty() || num != freq.get(size - 1)[0]) {freq.add(new int[]{num, 1});} else {++freq.get(size - 1)[1];}}dfs(0, target);return ans;}public void dfs(int pos, int rest) {if (rest == 0) {ans.add(new ArrayList<Integer>(sequence));return;}if (pos == freq.size() || rest < freq.get(pos)[0]) {return;}dfs(pos + 1, rest);int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);for (int i = 1; i <= most; ++i) {sequence.add(freq.get(pos)[0]);dfs(pos + 1, rest - i * freq.get(pos)[0]);}for (int i = 1; i <= most; ++i) {sequence.remove(sequence.size() - 1);}}}