子集、排列、组合

发表于 | 分类于 ， ， |

回溯算法解决子集、排列、组合问题

78.子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序返回解集。

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>> res;
    vector<int> temp;
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int start){
        //将结果加入到res中
        res.push_back(temp);
        for(int i=start;i<nums.size();i++){
            //做选择
            temp.push_back(nums[i]);
            //回溯
            dfs(nums, i+1);
            //撤消选择
            temp.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func subsets(nums []int) [][]int {
    var res [][]int
    var temp []int
    var dfs func([]int, int)
    dfs = func(nums []int, start int) {
        //将结果加入到res中
        res = append(res, append([]int{}, temp...))
        for i := start; i < len(nums); i++ {
            //做选择
            temp = append(temp, nums[i])
            //回溯
            dfs(nums, i+1)
            //撤消选择
            temp = temp[:len(temp)-1]
        }
    }
    dfs(nums, 0)
    return res
}

90.子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按任意顺序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        //将元素排序
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int start){
        res.push_back(temp);
        for(int i=start;i<nums.size();i++){
            //剪枝,值相同的相邻树枝，只遍历一次
            if(i>start && nums[i]==nums[i-1]) continue;
            //做选择
            temp.push_back(nums[i]);
            //回溯
            dfs(nums, i+1);
            //撤销选择
            temp.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
func subsetsWithDup(nums []int) [][]int {
    var res [][]int
    var temp []int
    //将元素排序
    sort.Ints(nums)
    var dfs func([]int, int)
    dfs = func(nums []int, start int) {
        res = append(res, append([]int{}, temp...))
        for i := start; i < len(nums); i++ {
            //剪枝,值相同的相邻树枝，只遍历一次
            if i > start && nums[i] == nums[i-1] {
                continue
            }
            //做选择
            temp = append(temp, nums[i])
            //回溯
            dfs(nums, i+1)
            //撤销选择
            temp = temp[:len(temp)-1]
        }
    }
    dfs(nums, 0)
    return res
}

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }
    void dfs(int n, int k, int start){
        //结束条件
        if(k==temp.size()){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<=n;i++){
            //做选择
            temp.push_back(i);
            //回溯
            dfs(n, k, i+1);
            //撤消选择
            temp.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func combine(n int, k int) [][]int {
    var res [][]int
    var temp []int
    var dfs func(int, int, int)
    dfs = func(n, k, start int) {
        //结束条件
        if k == len(temp) {
            res = append(res, append([]int{}, temp...))
            return
        }
        for i := start; i <= n; i++ {
            //做选择
            temp = append(temp, i)
            //回溯
            dfs(n, k, i+1)
            //撤消选择
            temp = temp[:len(temp)-1]
        }
    }
    dfs(n, k, 1)
    return res
}

39.组合总和

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

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    int sum=0;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);;
        return res;
    }
    void dfs(vector<int>& candidates, int target, int start){
        //结束条件
        if(sum>target){
            return;
        }
        if(sum==target){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<candidates.size();i++){
            //做选择
            temp.push_back(candidates[i]);
            sum += candidates[i];
            //回溯
            dfs(candidates, target, i);
            //撤消选择
            temp.pop_back();
            sum -= candidates[i];
        }
    }
};
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
func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    var temp []int
    sum := 0
    var dfs func([]int, int, int)
    dfs = func(candidates []int, target, start int) {
        //结束条件
        if sum > target {
            return
        }
        if sum == target {
            res = append(res, append([]int{}, temp...))
            return
        }
        for i := start; i < len(candidates); i++ {
            //做选择
            temp = append(temp, candidates[i])
            sum += candidates[i]
            //回溯
            dfs(candidates, target, i)
            //撤消选择
            temp = temp[:len(temp)-1]
            sum -= candidates[i]
        }
    }
    dfs(candidates, target, 0)
    return res
}

40.组合总和 II

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

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

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

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>> res;
    vector<int> temp;
    int sum=0;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return res;
    }
    void dfs(vector<int>& candidates, int target, int start){
        //结束条件
        if(sum>target){
            return;
        }
        if(sum==target){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<candidates.size();i++){
            //剪枝，值相同的树枝，只遍历第一条
            if(i>start && candidates[i]==candidates[i-1]) continue;
            //做选择
            temp.push_back(candidates[i]);
            sum += candidates[i];
            //回溯
            dfs(candidates, target, i+1);
            //撤消选择
            temp.pop_back();
            sum -= candidates[i];
        }

    }
};
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
func combinationSum2(candidates []int, target int) [][]int {
    var res [][]int
    var temp []int
    sum := 0
    sort.Ints(candidates)
    var dfs func([]int, int, int)
    dfs = func(candidates []int, target, start int) {
        //结束条件
        if sum > target {
            return
        }
        if sum == target {
            res = append(res, append([]int{}, temp...))
            return
        }
        for i := start; i < len(candidates); i++ {
            //剪枝，值相同的树枝，只遍历第一条
            if i > start && candidates[i] == candidates[i-1] {
                continue
            }
            //做选择
            temp = append(temp, candidates[i])
            sum += candidates[i]
            //回溯
            dfs(candidates, target, i+1)
            //撤消选择
            temp = temp[:len(temp)-1]
            sum -= candidates[i]
        }
    }
    dfs(candidates, target, 0)
    return res
}

216.组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    int sum=0;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return res;
    }
    void dfs(int k, int n, int start){
        //结束条件
        if(sum>n){
            return;
        }
        if(temp.size()==k && sum==n){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<=9;i++){
            //做选择
            temp.push_back(i);
            sum += i;
            //回溯
            dfs(k, n, i+1);
            //撤消选择
            temp.pop_back();
            sum -= i;
        }
    }
};
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
func combinationSum3(k int, n int) [][]int {
    var res [][]int
    var temp []int
    sum := 0
    var dfs func(int, int, int)
    dfs = func(k, n, start int) {
        //结束条件
        if sum > n {
            return
        }
        if len(temp) == k && sum == n {
            res = append(res, append([]int{}, temp...))
            return
        }
        for i := start; i <= 9; i++ {
            //做选择
            temp = append(temp, i)
            sum += i
            //回溯
            dfs(k, n, i+1)
            //撤消选择
            temp = temp[:len(temp)-1]
            sum -= i
        }
    }
    dfs(k, n, 1)
    return res
}

46.全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<bool> isVisited;
    vector<vector<int>> permute(vector<int>& nums) {
        int n=nums.size();
        isVisited.resize(n, false);
        dfs(nums);
        return res;
    }
    void dfs(vector<int>& nums){
        //触发结束条件
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return;
        }
        for(int i=0;i<nums.size();i++){
            //剪枝函数
            if(isVisited[i]) continue;
            //做选择
            isVisited[i]=true;
            temp.push_back(nums[i]);
            //回溯
            dfs(nums);
            //撤消选择
            temp.pop_back();
            isVisited[i]=false;
        }
    }
};
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
func permute(nums []int) [][]int {
    var res [][]int
    var temp []int
    n := len(nums)
    isVisited := make([]bool, n)
    var dfs func([]int)
    dfs = func(nums []int) {
        //触发结束条件
        if len(temp) == len(nums) {
            res = append(res, append([]int{}, temp...))
            return
        }
        for i := 0; i < len(nums); i++ {
            //剪枝函数
            if isVisited[i] {
                continue
            }
            //做选择
            isVisited[i] = true
            temp = append(temp, nums[i])
            //回溯
            dfs(nums)
            //撤消选择
            temp = temp[:len(temp)-1]
            isVisited[i] = false
        }
    }
    dfs(nums)
    return res
}

47.全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<bool> isVisited;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        //先排序，让相同的元素靠在一起
        sort(nums.begin(), nums.end());
        int n=nums.size();
        isVisited.resize(n, false);
        dfs(nums);
        return res;
    }
    void dfs(vector<int>& nums){
        //触发结束条件
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return;
        }
        for(int i=0;i<nums.size();i++){
            //剪枝
            if(isVisited[i]) continue;
            // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
            // 如果前面的相邻相等元素没有用过，则跳过
            if(i>0 && nums[i]==nums[i-1] && !isVisited[i-1]) continue; 
            //做选择
            isVisited[i]=true;
            temp.push_back(nums[i]);
            //回溯
            dfs(nums);
            //撤销选择
            temp.pop_back();
            isVisited[i]=false;
        }
    }
};
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
func permuteUnique(nums []int) [][]int {
    var res [][]int
    var temp []int
    //先排序，让相同的元素靠在一起
    sort.Ints(nums)
    n := len(nums)
    isVisited := make([]bool, n)
    var dfs func([]int)
    dfs = func(nums []int) {
        //触发结束条件
        if len(temp) == len(nums) {
            res = append(res, append([]int{}, temp...))
            return
        }
        for i := 0; i < len(nums); i++ {
            //剪枝
            if isVisited[i] {
                continue
            }
            // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
            // 如果前面的相邻相等元素没有用过，则跳过
            if i > 0 && nums[i] == nums[i-1] && !isVisited[i-1] {
                continue
            }
            //做选择
            isVisited[i] = true
            temp = append(temp, nums[i])
            //回溯
            dfs(nums)
            //撤销选择
            temp = temp[:len(temp)-1]
            isVisited[i] = false
        }
    }
    dfs(nums)
    return res
}

31.下一个排列

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
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //思路：两趟遍历
        //从后往前找到第一个逆序的数字，
        //然后找到该逆序数字后面比它大的最小数字
        //交换两个数的位置
        //对一开始逆序数位置后面的进行反转

        int i=nums.size()-2;
        //从后往前找到第一个逆序的数字
        while(i>=0 && nums[i]>=nums[i+1]){
            i--;
        }
        //找到该逆序数字后面比它大的最小数字
        if(i>=0){
            int j=nums.size()-1;
            while(j>=0 && nums[i]>=nums[j]){
                j--;
            }
            //交换
            swap(nums[i], nums[j]);
        }
        //对一开始逆序数位置后面的进行反转
        reverse(nums.begin()+i+1, nums.end());
    }
};
//时间复杂度：O(n)
//空间复杂度：O(1)
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
func nextPermutation(nums []int) {
    //思路：两趟遍历
    //从后往前找到第一个逆序的数字，
    //然后找到该逆序数字后面比它大的最小数字
    //交换两个数的位置
    //对一开始逆序数位置后面的进行反转

    i := len(nums) - 2
    //从后往前找到第一个逆序的数字
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    //找到该逆序数字后面比它大的最小数字
    if i >= 0 {
        j := len(nums) - 1
        for j >= 0 && nums[i] >= nums[j] {
            j--
        }
        //交换
        nums[i], nums[j] = nums[j], nums[i]
    }
    //对一开始逆序数位置后面的进行反转
    left, right := i+1, len(nums)-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}
//时间复杂度：O(n)
//空间复杂度：O(1)
-------------本文结束 感谢阅读-------------
0%