39. 组合总和

39. 组合总和

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

C++

//
// Created by 25678 on 2024/11/1.
//#ifndef GUC_39_组合总和_H
#define GUC_39_组合总和_H
#include <vector>;
#include <iostream>
#include <algorithm>using namespace std;class Solution {
private:vector<vector<int>> result;vector<int> path;/**** @param candidates* @param target* @param curSum* @param startIndex*/void backtracking(vector<int>& candidates,int target,int curSum,int startIndex){if(curSum==target){result.push_back(path);return;}for(int i=startIndex;i<candidates.size();i++) {if (curSum + candidates[i] > target) {return;}curSum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, curSum, i);curSum -= candidates[i];path.pop_back();  // 回溯，撤销选择的元素，保证不再使用该元素}}public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {result.clear();path.clear();// 将candidates从小到大排序sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return result;}
};
#endif //GUC_39_组合总和_H

java

package 代码随想录.回溯.第二遍;import java.util.*;public class _39组合总和 {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();/**** @param candidates    整数数组 candidates* @param target        目标整数 target* @return  找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合* candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。*/public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);    // 排序，方便剪枝backTracking(candidates,target,0,0);return res;}/*** 方法二：增加一个访问的索引，避免重复组合* @param candidates* @param target* @param curSum* @param startIndex 递归的起始索引，避免重复组合*/private void backTracking(int[] candidates, int target, int curSum, int startIndex) {if (curSum == target) {res.add(new ArrayList<>(path)); // 复制当前 path 并添加到 resreturn;} else if (curSum > target) {return;}// 遍历候选数组for (int i = startIndex; i < candidates.length; i++) {path.add(candidates[i]);curSum += candidates[i];backTracking(candidates, target, curSum, i); // 递归调用，传入当前索引 i 以允许重复选择path.remove(path.size() - 1); // 回溯curSum -= candidates[i];}}
}