帅气咕杂货间

leetcode39-组合总和题解

leetcode 39
Word count: 353 / Reading time: 2 min
2018/08/08 Share

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题解

常见的dfs递归问题,将问题进一步分解为是否将当前index指向的数字加入组合中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> result;
        vector<int> book;
        combinate(result, book, candidates, candidates.size() - 1, target);
        return result;
    }

private:
    void combinate(vector<vector<int>> &result, vector<int> &book, vector<int> &candidates, int index, int target) {
        if (target == 0) {
            result.push_back(book);
            return;
        }
        if (target < 0) {
            return;
        }

        if (index >= 0) {
            book.push_back(candidates[index]);
            combinate(result, book, candidates, index, target - candidates[index]);
            book.pop_back();
            combinate(result, book, candidates, index - 1, target);
        }
    }
    vector<vector<int>> getCartesianProduct(vector<vector<int>> &a, vector<vector<int>> &b) {
        vector<vector<int>> result;
        for (int i = 0; i < a.size(); i++) {
            for (int k = 0; k < b.size(); k++) {
                vector<int> temp;
                temp.insert(temp.end(), a[i].begin(), a[i].end());
                temp.insert(temp.end(), b[k].begin(), b[k].end());
                result.push_back(temp);
            }
        }
        return result;
    }
};

原文作者: Arch Yi

原文链接: http://watermelon1gugu.github.io/2018/08/08/leetcode39/

发表日期: August 8th 2018, 1:21:29 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 题解
Total : 34
2019
2018
百度 控诉 笔试 springBoot JPA TIM Leetcode 233 JVM memory model eps 进程间通信 HelloWorld 解决办法 isdc jetbrain leetcode 39 makefile 正则表达式 modelMapper mutex semaphore mapper mybatis oneToMany ubuntu18.04 mysql opencv mybatis-generator pip SpringBoot SpringMVC Mybatis stream C++ systemd ubuntu volatile 春招 后端 图谱