39. 组合总和，40. 组合总和 II，41. 缺失的第一个正数，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.17 可通过leetcode所有测试用例。
39. 组合总和
给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为
target的不同组合数少于150个。
示例 1：
输入：candidates =[2,3,6,7],target =7输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。示例 2：
输入: candidates = [2,3,5],target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3：
输入: candidates =[2],target = 1 输出: []
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
解题思路
对于这个问题，我们可以从空解开始，尝试每一个 candidates 中的数字，看它是否能够构成目标和。如果当前选择的数字和之前选择的数字的总和小于目标 target，我们可以继续选择相同的数字或下一个数字，因为题目中说明了同一个数字可以无限次重复选择。如果总和等于目标 target，则将当前解添加到结果列表中。如果总和大于 target，则回溯，尝试下一个数字。
解题步骤如下：
- 对
candidates进行排序，以便我们可以在总和超过target时提前终止搜索。 - 使用回溯法构建一个辅助函数来生成所有可能的组合。这个函数将会接收当前的组合、当前的总和、当前位置和目标
target。 - 在每次调用中，如果当前总和等于目标
target，则将当前组合添加到结果列表中。如果当前总和大于target，则终止当前分支。 - 从当前位置开始，递归地尝试每一个可能的选项，将当前数字添加到当前组合中，并更新当前总和。每次递归调用后，撤销上一次选择，以尝试下一个数字。
- 最终返回结果列表。
完整代码
Python
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start, path, target):
if target == 0:
result.append(list(path))
return
if target < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, target - candidates[i]) # 不增加i的值来允许数字重复选择
path.pop() # 回溯
result = []
candidates.sort() # 排序有助于提前终止搜索
backtrack(0, [], target)
return resultJava
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates); // 排序有助于提前终止搜索
backtrack(result, new ArrayList<>(), candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
if (remain == 0) {
result.add(new ArrayList<>(tempList));
} else if (remain < 0) {
return;
} else {
for (int i = start; i < candidates.length; i++) {
tempList.add(candidates[i]);
backtrack(result, tempList, candidates, remain - candidates[i], i); // 不增加i的值来允许数字重复选择
tempList.remove(tempList.size() - 1); // 回溯
}
}
}
}
40. 组合总和 II
给定一个候选人编号的集合
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 <= 1001 <= candidates[i] <= 501 <= target <= 30
解题思路
这个问题与之前的问题类似，但有一个关键的区别：每个数字在每个组合中只能使用一次。我们仍然可以使用回溯法来解决这个问题，但需要添加一些额外的步骤来确保不会有重复的组合。
解题步骤如下：
- 对
candidates进行排序，这样有助于我们在递归时跳过重复的数字，以避免产生重复的组合。 - 使用回溯法构建一个辅助函数来生成所有可能的组合。这个函数将会接收当前的组合、当前的总和、当前位置和目标
target。 - 在每次调用中，如果当前总和等于目标
target，则将当前组合添加到结果列表中。如果当前总和大于target，则终止当前分支。 - 从当前位置的下一个位置开始，递归地尝试每一个可能的选项，将当前数字添加到当前组合中，并更新当前总和。这一步确保了每个数字在每个组合中只使用一次。
- 为了避免重复的组合，每次在递归的同一层级中，如果遇到与之前相同的数字，则跳过这个数字。
- 每次递归调用后，撤销上一次选择，以尝试下一个数字。
- 最终返回结果列表。
完整代码
Python
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start, path, target):
if target == 0:
result.append(list(path))
return
if target < 0:
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue # 跳过重复的数字
path.append(candidates[i])
backtrack(i + 1, path, target - candidates[i]) # i + 1 确保每个数字只用一次
path.pop() # 回溯
result = []
candidates.sort() # 排序有助于提前终止搜索
backtrack(0, [], target)
return resultJava
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates); // 排序有助于提前终止搜索
backtrack(result, new ArrayList<>(), candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
if (remain == 0) {
result.add(new ArrayList<>(tempList));
} else if (remain < 0) {
return;
} else {
for (int i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) continue; // 跳过重复的数字
tempList.add(candidates[i]);
backtrack(result, tempList, candidates, remain - candidates[i], i + 1); // i + 1 确保每个数字只用一次
tempList.remove(tempList.size() - 1); // 回溯
}
}
}
}
41. 缺失的第一个正数
给你一个未排序的整数数组
请你实现时间复杂度为nums，请你找出其中没有出现的最小的正整数。O(n)并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
解题思路
这个问题可以通过 "原地哈希" 的方式来解决。原地哈希通常指的是直接在输入数组上进行操作，而不使用额外的空间来存储数据。由于我们只关心最小的未出现的正整数，我们可以尝试将数组中所有的正整数 n 放到数组的 n-1 位置上。这样，如果数组是完全按顺序的（即 nums[i] = i + 1），我们就知道数组中包含了所有从 1 到 n 的正整数，因此未出现的最小正整数就是 n + 1。
解题步骤如下：
- 遍历数组，对于每个数字，如果它在
1到n的范围内，并且它不在正确的位置上（即nums[i] != nums[nums[i] - 1]），则将其与正确位置上的数字交换。这个步骤可能需要多次交换才能将一个数字放到正确的位置。 - 再次遍历数组，第一个不满足
nums[i] = i + 1的位置i，其对应的最小未出现正整数就是i + 1。 - 如果所有位置都满足
nums[i] = i + 1，则数组中的最小未出现的正整数是n + 1。
完整代码
Python
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1Java
public class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
