39/40/216-组合总和

LeetCode

发布日期: 2021-06-23

LeetCode 39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

method: 回溯

因为不限次数，所以下次还是可以从i开始取
加上nums[i]转换成target-nums[i]，可以减少一个参数，最后target=0就行
剪枝：target-nums[i]必须大于0，小于0说明取的数的总和已经超过target了，元素又都是正数，所以没必要再取了

vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, int target, int index) {
    if (target == 0) {  // 减到等于0就可以了
        ret.push_back(path);
        return;
    }
    for (int i = index; i < nums.size() && target > 0; ++i) {
        path.push_back(nums[i]);
        dfs(nums, target - nums[i], i);    // 可以从i再继续取
        path.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
    dfs(nums, target, 0);
    return ret;
}

LeetCode 40. Combination Sum II

LeetCode-40

Given a collection of candidate numbers and a target number, find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

method

与39题不同之处：

只能使用一次，所以从i + 1开始取
数组有重复，但是组合不能重复

[1, 1, 2]不能出现[1, 2], [1, 2]，尽管是不同的1

先排序让相同的元素排在一起
index=0的时候，如果i=1 && nums[i]==nums[i - 1]，说明出现了重复

vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, int target, int index) {
    if (target == 0) {
        ret.push_back(path);
        return;
    }
    for (int i = index; i < nums.size() && target > 0; ++i) {
        if (i > index && nums[i] == nums[i - 1])
            continue;   // 同一个树杈的去重
        path.push_back(nums[i]);
        dfs(nums, target - nums[i], i + 1);
        path.pop_back();
    }
}
vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    dfs(nums, target, 0);
    return ret;
}

也可以用排序+used数组，或者哈希表，但是也要排序，不排序的话虽然树杈去重了，但是子树上可能还会选到

LeetCode 216. Combination Sum III

LeetCode-216

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7

method: 回溯+剪枝

1-9数组大小固定，选择大小k固定，且只能用一次

path大小固定为k

终止条件path.size() == k
剪枝i <= nums.size() - (k - path.size()) + 1和target > 0

vector<vector<int>> ret;
vector<int> path;
void dfs(int k, int target, int index) {
    if (path.size() == k) {     // 取了k个不管怎样都要返回
        if (target == 0) ret.push_back(path);
        return;
    }
    for (int i = index; i <= 9 - (k - path.size()) + 1 && target > 0; ++i) {
        path.push_back(i);
        dfs(k, target - i, i + 1);
        path.pop_back();
    }
}
vector<vector<int>> combinationSum3(int k, int n) {
    dfs(k, n, 1);
    return ret;
}