DFS求集合的各种变形

Posted on   |   In   |   visited:  

DFS适用于求组合，输出全部答案的场景。
本次包含leetcode题目 Subsets, Combinations, Combination Sum, Combination Sum II, Combination Sum III, Combination Sum IV。 注意，最后一个也是集合题目，但求的是集合数目，用动态规划的方法。

（1）求一个数组的全部子集组合

  • 深搜方法：
    ［］
    ［1］［1，2］［1，2，3］［1，3］
    ［2］［2，3］
    ［3］
  • 递归元素添加：
    ［］
    ［1］
    ［2］［1，2］
    ［3］［1，3］［2，3］［1，2，3］

（2）求一个数组符合条件（比如元素个数为2个）的特定子集组合
（3）求从一个数组中选出几个数，和为特定值的组合，元素允许重复使用（是否默认输入数组无重复元素），结果集不允许存在重复组合.

1
2
3
4
5
6
7
8
9
10
11
12
if(target == 0){
     allSets.push_back(sol);
     return;
}
for(int j=i; j<candidates.size();j++){
    if(candidates[j] > target){
        continue;
    }
    sol.push_back(candidates[j]);
    findAllSets(candidates, j, target-candidates[j], sol, allSets //注意允许同一个元素重复使用
    sol.pop_back();
}

（4）求从一个数组中选出几个数，和为特定值的组合，元素不允许重复使用（是否默认输入数组可能存在重复元素），结果集不允许存在重复组合.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(target == 0){
    allSets.push_back(sol);
    return;
}
for(int j=i; j<candidates.size();j++){
    if(candidates[j] > target ){ //或者在for循环外面加一层if(target < 0) continue;
        continue;
    }
    if(j!=i && candidates[j] == candidates[j-1]) //避免重复结果组合的出现
        continue;
    sol.push_back(candidates[j]);
    findAllSets(candidates, j+1, target-candidates[j], sol, allSets); //注意同一个元素不允许重复使用
    sol.pop_back();
}

(5) 求从1-9中选出k个数，和n的组合，（4）的变形。

详细的题目讲解

(1) 求所有子集

/元素添加的方式最容易理解
[]
[],[1]
[],[1],[2],[1,2]
[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3] /

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> part;
        res.push_back(part);
        if(nums.size() == 0){
            return res;
        }
        vector<int>::iterator it;
 
        for(it=nums.begin(); it != nums.end(); it++){
            int n = res.size();
            for (int j =0; j< n; j++){
                part = res[j];
                part.push_back(*it);
                res.push_back(part);
            }
        }
        return res;
    }
};

DFS 递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> allSets;
        vector<int> sol;
        findAllSets(n, 1, k, sol, allSets);
        return allSets;
    }
    void findAllSets(int n, int i, int k, vector<int>& sol, vector<vector<int>>& allSets){
        for(int j = i; j<=n;j++){
            sol.push_back(j);
            allSets.push_back(sol);
            findAllSets(n, j+1, k, sol, allSets);
            sol.pop_back();
        }
    }
};

(2）求一个数组符合条件（比如元素个数为2个）的特定子集组合

注意：阿里2017二面题，已哭。
/*
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> allSets;
        vector<int> sol;
        findAllSets(n, 1, k, sol, allSets);
        return allSets;
    }
    void findAllSets(int n, int i, int k, vector<int>& sol, vector<vector<int>>& allSets){
        for(int j = i; j<=n;j++){
            if(sol.size() < k){
                sol.push_back(j);
                if(sol.size() == k){
                    allSets.push_back(sol);
                }
                findAllSets(n, j+1, k, sol, allSets);
                sol.pop_back();
            }
        }
    }
};

(3）求从一个数组中选出几个数，和为特定值的组合，元素允许重复使用（是否默认输入数组无重复元素），结果集不允许存在重复组合.

/*
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations. //并结果集合不允许重复
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
此题的问题是：输入是不是默认没有重复元素，如果有的话结果也是需要去重的。答案没处理去重，所有的测试用例也过了。。。
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> sol;
        vector<vector<int>> allSets;
        findAllSets(candidates, 0, target, sol, allSets);
        return allSets;
    } 
    void findAllSets(vector<int>& candidates, int i, int target, vector<int>& sol, vector<vector<int>>& allSets){
        if(target == 0){
             allSets.push_back(sol);
             return;
        }
        for(int j=i; j<candidates.size();j++){
            if(candidates[j] > target){
                continue;
            }
            sol.push_back(candidates[j]);
            findAllSets(candidates, j, target-candidates[j], sol, allSets //注意允许同一个元素重复使用
            sol.pop_back();
        }
    }
};

####（4）求从一个数组中选出几个数，和为特定值的组合，元素不允许重复使用（是否默认输入数组可能存在重复元素），结果集不允许存在重复组合.

同上一题，但是不允许同一个元素重复使用（需要先排序），并结果集合不允许重复

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
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> sol;
        vector<vector<int>> allSets;
        sort(candidates.begin(), candidates.end()); //不允许重复，先排序
        findAllSets(candidates, 0, target, sol, allSets);
        return allSets;
    } 
    void findAllSets(vector<int>& candidates, int i, int target, vector<int>& sol, vector<vector<int>>& allSets){
        map<vector<int>, int> myMap;
        if(target == 0){
             int k = 0;
             for(k = 0; k< allSets.size(); k++){ //查找是否已存在
                 if (sol == allSets[k]){
                     break;
                 }
             }
             if(k == allSets.size()) {//不存在,加入
                myMap[sol] = 1;
                allSets.push_back(sol);
             }
             return;
        }
        for(int j=i; j<candidates.size();j++){
            if(candidates[j] > target){
                continue;
            }
            sol.push_back(candidates[j]);
            findAllSets(candidates, j+1, target-candidates[j], sol, allSets); //注意不允许同一个元素重复使用（j和j+1的区别）
            sol.pop_back();
        }
    }
};

// 另外一种控制重复的通用方法，下面的题会反复用到

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
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> sol;
        vector<vector<int>> allSets;
        sort(candidates.begin(), candidates.end()); //先排序
        findAllSets(candidates, 0, target, sol, allSets);
        return allSets;
    } 
    void findAllSets(vector<int>& candidates, int i, int target, vector<int>& sol, vector<vector<int>>& allSets){
        if(target == 0){
            allSets.push_back(sol);
            return;
        }
        for(int j=i; j<candidates.size();j++){
            if(candidates[j] > target){
                continue;
            }
            if(j!=i && candidates[j] == candidates[j-1]) //避免重复结果
                continue;
            sol.push_back(candidates[j]);
            findAllSets(candidates, j+1, target-candidates[j], sol, allSets); //注意同一个元素不允许重复使用
            sol.pop_back();
        }
    }
};

(5) 求从1-9中选出k个数，和n的组合，（4）的变形。

/*
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]
*/

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
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> sol;
        vector<vector<int>> allSets;
        findAllSets(k, n, 1, sol, allSets);
        return allSets;
    } 
    void findAllSets(int k, int n, int i, vector<int>& sol, vector<vector<int>>& allSets){
        if(n == 0){
            if(sol.size() == k)
                allSets.push_back(sol);
            return;
        }
        if (sol.size() > k || i>9 )
            return;
        for(int j=i; j<=9;j++){
            if(j > n){
                continue;
            }
            sol.push_back(j);
            findAllSets(k, n-j, j+1, sol, allSets); 
            sol.pop_back();
        }
    }
};

(6) 所有可能的组合数目，和为某个值，元素可重复使用

/*
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?
*/

遇到求集合总数的题目，条件反射动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> res(target+1);
        res[0] = 1;
        if(nums.size() == 0){
            return 0;
        }
        sort(nums.begin(), nums.end());
        for(int i = 1; i<=target; i++){
            for(int j=0;j<nums.size();j++){
                if(i >= nums[j])
                    res[i] = res[i] + res[i-nums[j]];
                else
                     break;
            }
        }
        return res[target];
    }

(7). 加一道类似的微软二面面试题

一个含有n个集合的集合(集合的元素多个集合),对这个集合中的元素合并，合并策略：如果两个元素(集合)存在交集，则合并为一个集合，最后的新元素个数为m个。
问题1. m是不是一定存在稳定状态，所谓的不稳定状态是指，一直存在交集，需要一直合并
问题2. m是唯一的吗？
问题3. 代码实现

前两个问题利用假设不存在的方法证明
问题3的代码实现类似于最简单的combinations，留作思考。

总结：求组合，输出全部答案，想到dfs；求总数，条件反射dp。万变不离其宗，记住一种解法，比如列表的所有集合，剩下的是举一反三的推演。