岳池发展建设集团有限公司门户网站,ci设计,123网页浏览器,辽阳公司网站建设39 组合总和
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以…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
题目分析
本题没有数量要求可以无限重复但是有总和的限制所以间接的也是有个数的限制。
前端时间忙工作落下了不少分析后面就简略了
acm模式代码
#include iostream
#include vectorclass Solution{
private:std::vectorstd::vectorint result;std::vectorint path;void backtracking(std::vectorint candidates, int target, int sum, int startIndex) {if (sum target) {return;}if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size(); i) {sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 不用i 1表示可以重复读取当前数字sum - candidates[i];path.pop_back();}}
public:std::vectorstd::vectorint combinationSum(std::vectorint candidates, int target) {result.clear();path.clear();backtracking(candidates, target, 0, 0);return result;}};int main() {Solution sol;std::vectorint candidates {2, 3, 6, 7};int target 7;std::vectorstd::vectorint result sol.combinationSum(candidates, target);std::cout Combinations summing to target :\n;for (const auto combination : result) {std::cout [;for (size_t i 0; i combination.size(); i) {std::cout combination[i];if (i combination.size() - 1) std::cout , ;}std::cout ]\n;}return 0;
}
40 组合总和
题目描述
给定一个候选人编号的集合 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
题目分析
本题的难点在于区别2中集合数组candidates有重复元素但还不能有重复的组合。所以我们要去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。
此题还需要加一个bool型数组used用来记录同一树枝上的元素是否使用过。
这个集合去重的重任就是used来完成的。
acm模式代码
#include iostream
#include vector
#include algorithmclass Solution{
private:std::vectorstd::vectorint result;std::vectorint path;void backtracking(std::vectorint candidates, int target, int sum, int startIndex, std::vectorbool used) {if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) {// used[i - 1] true说明同一树枝candidates[i - 1]使用过// used[i - 1] false说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i 0 candidates[i] candidates[i -1] used[i -1] false) {continue;}sum candidates[i];path.push_back(candidates[i]);used[i] true;backtracking(candidates, target, sum, i 1, used);used[i] false;sum - candidates[i];path.pop_back();}}
public:std::vectorstd::vectorint combinationSum2(std::vectorint candidates, int target) {std::vectorbool used(candidates.size(), false);path.clear();result.clear();sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0 ,0, used);return result;}
};int main() {Solution sol;std::vectorint candidates {10, 1, 2, 7, 6, 1, 5};int target 8;std::vectorstd::vectorint result sol.combinationSum2(candidates, target);std::cout 所有组合的数字之和等于 target 的唯一组合为:\n;for (const auto combination : result) {std::cout [;for (size_t i 0; i combination.size(); i) {std::cout combination[i];if (i combination.size() - 1) std::cout , ;}std::cout ]\n;}return 0;
}
131 分割回文串
题目描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。 示例 1
输入s aab
输出[[a,a,b],[aa,b]]示例 2
输入s a
输出[[a]]提示
1 s.length 16s 仅由小写英文字母组成
题目分析
根据回溯算法模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}
acm完整代码
#include iostream
#include vector
// #include stringclass Solution{
private:std::vectorstd::vectorstd::string result;std::vectorstd::string path;void backtracking(const std::string s, int startIndex) {//如果起始位置已经大于s的大小了说明已经找到一组分割方案了if(startIndex s.size()) {result.push_back(path);return;}for (int i startIndex; i s.size(); i) {if (isPalindrome(s,startIndex, i)){//获取[startindex,i]在s中的子串std::string str s.substr(startIndex, i - startIndex 1);path.push_back(str);}else {continue;}backtracking(s, i 1);path.pop_back();}}bool isPalindrome(const std::string s , int start, int end) {for ( int i start, j end; i j; i , j--) {if(s[i] ! s[j]) {return false;}}return true;}
public:std::vectorstd::vectorstd::string partirion(std::string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};int main() {Solution solution;std::string s aab;std::vectorstd::vectorstd::string partitions solution.partirion(s);std::cout 所有可能的回文分割方式:\n;for (const auto partition : partitions) {for (const auto str : partition) {std::cout str ;}std::cout \n;}return 0;
}
