leetcode39：组合总和

题目链接

leetcode

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    回溯，深度优先搜索 DFS

    时间复杂度：O(2^n)
        其中 n 是候选数字的数量。
        在最坏的情况下，每个数字都有两种选择：选择或不选择，共有 2^n 种组合。
    空间复杂度：O(m)
        其中 m 是结果列表中元素的平均长度。
*/
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        if (candidates.empty()) {
            return result;
        }

        backtracking(candidates, target, 0, 0);

        return result;
    }

    void backtracking(vector<int>& candidates, int target, int sum, int start) {
        // 剪枝条件：超过目标和
        if (sum > target) {
            return;
        }
        // 结束条件：找到目标和
        if (sum == target) {
            result.push_back(path);
            return;
        }
        
        for (int i = start; 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();
        }
    }

private:
    vector<vector<int>> result;
    vector<int> path;
};

/*
    前一个版本的代码，对于 sum 大于 target 情况，仍然进入了下一层递归，
    下一层递归结束的时候，判断 sum > target 才返回。

    如果已知下一层 sum 大于 target，就没有必要进入下一层递归，
    可以在 for 循环时候进行限制。
*/
class Solution_1 {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        if (candidates.empty()) {
            return result;
        }

        sort(candidates.begin(), candidates.end()); // 排序，数组的有序性来提前终止不必要的递归
        backtracking(candidates, target, 0, 0);

        return result;
    }

    void backtracking(vector<int>& candidates, int target, int sum, int start) {
        // 结束条件：找到目标和
        if (sum == target) {
            result.push_back(path);
            return;
        }
        
        for (int i = start; i < candidates.size(); i++) {
            // 剪枝条件：超过目标和
            if (sum + candidates[i] > target) {
                break;
            }

            // 选择
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 不用i+1，表示可以重复读取当前的数字
            // 撤销选择：回溯
            sum -= candidates[i];
            path.pop_back();
        }
    }

private:
    vector<vector<int>> result;
    vector<int> path;
};

// 辅助函数：打印数组
void printArray(vector<int>& nums) {
	cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size()-1) {
            cout << ",";
        }
    }
    cout << "]";
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> candidates_cases = {
        {2,3,6,7},
        {2,3,5},
        {2}
    };
    vector<int> target_cases = {
        7, 8, 1
    };

    for (size_t i = 0; i < candidates_cases.size(); i++) {
        auto& candidates = candidates_cases[i];
        int target = target_cases[i];
        
        cout << "Input: candidates = ";
        printArray(candidates);
        cout << ", target = " << target << endl;

        vector<vector<int>> result = solution.combinationSum(candidates, target);
        cout << "Output: ";
        printArray(result);
        cout << endl;
    }

    return 0;
}