Day23- 回溯算法part03

2024-01-08 16:39:42

一、组合总和

题目一:39. 组合总和

39. 组合总和

给你一个?无重复元素?的整数数组?candidates?和一个目标整数?target?,找出?candidates?中可以使数字和为目标数?target?的 所有?不同组合?,并以列表形式返回。你可以按?任意顺序?返回这些组合。

candidates?中的?同一个?数字可以?无限制重复被选取?。如果至少一个数字的被选数量不同,则两种组合是不同的。?

对于给定的输入,保证和为?target?的不同组合数少于?150?个。

  • combinationSum 函数初始化必要的变量并开始回溯过程。
  • backtrack 函数是递归函数,它尝试添加数组中的每个元素到当前组合中,同时确保总和不超过目标数。如果总和达到目标数,就将当前组合添加到结果列表中。这个过程中,通过不断地添加和移除元素,探索所有可能的组合。
/*
 * @lc app=leetcode.cn id=39 lang=cpp
 *
 * [39] 组合总和
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> combination;
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, results, combination, 0);
        return results;
    }

private:
    void backtrack(const vector<int>& candidates, int target, vector<vector<int>>& results, vector<int>& combination, int start) {
        if (target == 0) {
            results.push_back(combination);
            return;
        }

        for (int i = start; i < candidates.size() && target - candidates[i] >= 0; ++i) {
            combination.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], results, combination, i); 
            combination.pop_back(); 
        }
    }
};
// @lc code=end

二、组合总和

题目一:40. 组合总和II

40. 组合总和 II

给定一个候选人编号的集合?candidates?和一个目标数?target?,找出?candidates?中所有可以使数字和为?target?的组合。

candidates?中的每个数字在每个组合中只能使用?一次?。

注意:解集不能包含重复的组合

  • 首先对 candidates 进行排序,以方便处理重复元素。
  • backtrack 函数中,使用一个循环来遍历 candidates,并且在每次迭代中检查是否需要跳过重复的元素。同时,递归地调用 backtrack 函数,每次调用时将 start 索引加一,确保每个数字在组合中只使用一次。
/*
 * @lc app=leetcode.cn id=40 lang=cpp
 *
 * [40] 组合总和 II
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, current, results);
        return results;
    }

private:
    void backtrack(vector<int>& candidates, int target, int start, vector<int>& current, vector<vector<int>>& results) {
        if (target == 0) {
            results.push_back(current);
            return;
        }

        for (int i = start; i < candidates.size() && target >= candidates[i]; ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;

            current.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, current, results);
            current.pop_back();
        }
    }
};
// @lc code=end

三、分割回文串

题目一:131. 分割回文串

131. 分割回文串

给你一个字符串?s,请你将?s?分割成一些子串,使每个子串都是?回文串?。返回?s?所有可能的分割方案。

回文串?是正着读和反着读都一样的字符串。

  • partition 函数初始化必要的变量并开始回溯过程。
  • backtrack 函数是递归函数,用于探索所有可能的子串组合。每当找到一个回文子串时,就将其加入当前列表并继续探索剩余的字符串。
  • isPalindrome 函数用于检查给定的字符串范围内的子串是否是回文。
/*
 * @lc app=leetcode.cn id=131 lang=cpp
 *
 * [131] 分割回文串
 */

// @lc code=start
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> results;
        vector<string> currentList;
        backtrack(s, 0, currentList, results);
        return results;
    }

private:
    void backtrack(const string& s, int start, vector<string>& currentList, vector<vector<string>>& results) {
        if (start >= s.size()) {
            results.push_back(currentList);
            return;
        }

        for (int end = start; end < s.size(); ++end) {
            if (isPalindrome(s, start, end)) {
                currentList.push_back(s.substr(start, end - start + 1));
                backtrack(s, end + 1, currentList, results);
                currentList.pop_back();
            }
        }
    }

    bool isPalindrome(const string& s, int low, int high) {
        while (low < high) {
            if (s[low] != s[high]) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
};
// @lc code=end

?

文章来源:https://blog.csdn.net/m0_66690787/article/details/135458223
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。