Java教程

子集中的回溯问题

本文主要是介绍子集中的回溯问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

子集中的回溯问题

例题一:子集||(力扣90)
子集||
题目描述:
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

示例一:

输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例二:

输入:nums = [0]
输出:[[],[0]]

提示:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

题目分析:
本题为之前写过的子集的变式,【力扣78】只是在之前的基础上增加了去重的步骤,而这也是本题的难点。子集的思路是先画出树形结构图,在树形结构图上进行分析会比较明了,所以我们画出本题的树形结构图:
在这里插入图片描述
本题去重就是在树形结构图中,同一树层上元素不能重复使用,但是同一树枝是可以重复的。
去重的思路有两种,一是标记数组,标记重复元素,有重复就跳过。二是直接遇到重复元素时跳过,基本思路都一致。

class Solution {
    vector<vector<int>>result;
    void backtricking(vector<int>&temp,vector<int>&nums,int i){
        if(i==nums.size()){
            result.push_back(temp);
        }
        else{
            temp.push_back(nums[i]);
            backtricking(temp,nums,i+1);
            temp.pop_back();
            while(i+1<nums.size()&&nums[i]==nums[i+1]){
                i++;
            }
                backtricking(temp,nums,i+1);
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            if(nums.size()==0){
                return {{}};
            }
            vector<int>tmp;
            backtricking(tmp,nums,0);
            return result;
    }
};
这篇关于子集中的回溯问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!