代码随想录 | Day31 | 回溯算法：子集问题

主要学习内容：

1.子集问题

2.复习树层去重

90.子集II

90. 子集 II - 力扣（LeetCode）

解法思路：

这个是数层间去重，不是树枝去重，即如图所示这样

树枝去重我们传入的参数index赋值为i+1而不是i就已经防止了树枝去重，而在树层去重，是在同一层不能选重复的，我们之前说过，一个for循环可以产生一层的结点。现在要在同一层不能选重复的，那说明，在for循环里面选择过的数（比如在i=0时压入了path），在本层函数的for循环其他时候不能压入path。

1.函数参数和返回值

1
2
vector<vector<int>> res;
void backtracking(vector<int> path,int index,vector<int> nums,vector<bool> used)

res存放结果

path存放目前放入的数

index为开始的结点，从index开始循环

nums题目数组

2.终止条件

本题是在每个结点都要收集答案，而不是叶子结点，所以终止条件就是for循环结束，不用加别的

3.本层代码逻辑

1
2
3
4
 // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
 // used[i - 1] == false，说明同一树层false[i - 1]使用过
 // 而我们要对同一树层使用过的元素进行跳过
//所以要再加一个条件就是nums[i]==nums[i-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void backtracking(vector<int> path,int index,vector<int> nums,vector<bool> used)
   {
       res.push_back(path);
       for(int i=index;i<nums.size();i++)
       {
           if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)
               continue;
           path.push_back(nums[i]);
           used[i]=true;
           backtracking(path,i+1,nums,used);
           path.pop_back();
           used[i]=false;
       }
   }

要注意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
class Solution {
public:
    vector<vector<int>> res;
    void backtracking(vector<int> path,int index,vector<int> nums,vector<bool> used)
    {
        res.push_back(path);
        for(int i=index;i<nums.size();i++)
        {
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)
                continue;
            path.push_back(nums[i]);
            used[i]=true;
            backtracking(path,i+1,nums,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(),false);
        sort(nums.begin(),nums.end());
        backtracking(path,0,nums,used);
        return res;
    }
};

哈希表版本：

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
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        unordered_set<int> uset;
        for (int i = startIndex; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0);
        return result;
    }
};

491.非递减子序列

491. 非递减子序列 - 力扣（LeetCode）

思路：

其实就是一个子集问题，只不过nums[i]压入path（当前已经收集的数）的时候有了条件，要求是非严格单调递增，那自然而然可以想到nums[i]大于等于path最后一个数才会被压入path，因为path前面的数都是这么压进去的，所以最后一个数肯定是最大的，不用管和前面的数的大小关系

特殊情况，如果path里面没数字，那就直接往里面放数字就完事

1.函数返回值和参数

1
2
vector<vector<int>> res;
void backtracking(vector<int> nums,vector<int> path,int index)

res记录结果

path当前已经收集的数

index每层开始遍历的数的下标

2.终止条件

本题是在各个结点都要收集结果，终止条件就是for循环结束条件

因为是子序列，所以至少有两个数才会被压入res结果集

1
2
if(path.size()>=2)
	res.push_back(path);

3.本层逻辑

和上面思路所说，第一种情况，path为空，直接往里面放数字就行

1
2
3
4
5
6
if(path.size()==0)
         {
             path.push_back(nums[i]);
             backtracking(nums,path,i+1);
             path.pop_back();
         }

第二种，只有要放入的数nums[i]大于等于path最后一个数才会被放入

1
2
3
4
5
6
else if(nums[i]>=path[path.size()-1])
          {
              path.push_back(nums[i]);
              backtracking(nums,path,i+1);
              path.pop_back();
          }

注意：本层的数层去重不能用nums[i-1]=num[i]这种，因为子序列可以不连续，并且原数组也不能排序，所以只能用哈希

1
2
3
if (uset.find(nums[i]) != uset.end())
	continue;
uset.insert(nums[i]);

完整本层逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
unordered_set<int> uset;
      for(int i=index;i<nums.size();i++)
      {
          if(path.size()==0)
          {
               if (uset.find(nums[i]) != uset.end())
                  continue;
              uset.insert(nums[i]);
              path.push_back(nums[i]);
              backtracking(nums,path,i+1);
              path.pop_back();
          }
          else if(nums[i]>=path[path.size()-1])
          {
               if (uset.find(nums[i]) != uset.end()) 
                  continue;
              uset.insert(nums[i]);
              path.push_back(nums[i]);
              backtracking(nums,path,i+1);
              path.pop_back();
          }
      }

可以整合一下代码逻辑：

1
2
3
4
5
6
7
8
9
10
11
unordered_set<int> uset;
for(int i=index;i<nums.size();i++)
{
    //非空的时候，小于path最后一个数 或者 重复了，那就跳过进入下一个
	if((!path.empty()&&nums[i]<path.back()) || (uset.find(nums[i])!=uset.end()))
		continue;
	uset.insert(nums[i]);
	path.push_back(nums[i]);
	backtracking(nums,path,i+1);
	path.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
class Solution {
public:
    vector<vector<int>> res;
    void backtracking(vector<int> nums,vector<int> path,int index)
    {
        if(path.size()>=2)
            res.push_back(path);
        unordered_set<int> uset;
        for(int i=index;i<nums.size();i++)
        {
            if((!path.empty()&&nums[i]<path.back()) || (uset.find(nums[i])!=uset.end()))
                continue;
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums,path,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> path;
        backtracking(nums,path,0);
        return res;
    }
};