dfs以及搜索问题

发表于 | 分类于

dfs以及搜索问题

DFS是搜索的手段之一。它从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态。直到找到最终的解。

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

C++可以用库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;        
        sort(nums.begin(),nums.end());//先排序
        do
        {
            res.push_back(nums);
        }while(next_permutation(nums.begin(),nums.end()));
        return res;

        
    }
};

另一种全排列的方法，回溯的思想

思路来源于网友们。

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:
    void backsee(int n,vector<vector<int>>& res,vector<int>& nums,int index){
        if(index==n)
            res.push_back(nums);
        for(int i=index;i<n;i++){//可以想象第一个数有n种选择，第二个数位置就是n-1种了
            swap(nums[i],nums[index]);
            backsee(n,res,nums,index+1);//问题缩小到第二个数
            swap(nums[i],nums[index]);
        }
        
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        //类似搜索树
        vector<vector<int>> res;  
        backsee(nums.size(),res,nums,0);
        return res;

        
    }
};

带剪枝的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

1、使用了STL 的count函数来剪枝，然后时间复杂度惊人。

执行用时 :2280 ms, 在所有 C++ 提交中击败了5.03%的用户

内存消耗 :10 MB, 在所有 C++ 提交中击败了65.48%的用户

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:
   void backsee(int n,vector<vector<int>>& res,vector<int>& nums,int index){
       //参数：总长度n,结果res,中间结果nums,index
        if(index==n&&count(res.begin(),res.end(),nums)==0)
            res.push_back(nums);
        for(int i=index;i<n;i++){//可以想象第一个数有n种选择，第二个数位置就是n-1种了
            swap(nums[i],nums[index]);
            backsee(n,res,nums,index+1);//问题缩小到第二个数
            swap(nums[i],nums[index]);
        }
        
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        //题目思路，看题解，可用set<vector>剔除重复的
        
        vector<vector<int>> res;
        backsee(nums.size(),res,nums,0);
        return res;
        
    }
};

2、使用C++自带全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
可以使用next_permutation，前提是先从小到大排序，该函数输出的就是无重复的全排列，运行时间24ms，击败98.87%。
vector<vector<int>> permuteUnique(vector<int>& nums)
{
	sort(nums.begin(), nums.end());
	vector<vector<int>>result;
	result.push_back(nums);
	while (next_permutation(nums.begin(), nums.end()))
	{
		result.push_back(nums);
	}
	return result;
}
去重，考虑重复的定义，其实就是同一位选进去了多个相同的数，换句话说就是若要不重复，同一位对同样的数只能使用一个，因此我们可以在每次DFS之前，也就是为本位置选数之前，判断是否已经使用过相同的数了，若没有则正常DFS，若有则跳过本次循环，这样不仅去掉了重复，而且减少了递归次数。
作者：luo-ben-zhu-xiao-man-tou
链接：https://leetcode-cn.com/problems/permutations-ii/solution/dfsqu-zhong-huo-zhe-shi-yong-czi-dai-quan-pai-lie-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3、参考了评论区大佬

用map进行改进

执行用时 :8 ms, 在所有 C++ 提交中击败了95.62%的用户

内存消耗 :11.1 MB, 在所有 C++ 提交中击败了25.72%的用户

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:
   void backsee(int n,vector<vector<int>>& res,vector<int>& nums,int index,int used[]){
       //参数：总长度n,结果res,中间结果nums,index
        map<int,int> ex;
        if(index==n)
            res.push_back(nums);
        for(int i=index;i<n;i++){//可以想象第一个数有n种选择，第二个数位置就是n-1种了
            // cout<<i<<endl;
            if(ex.count(nums[i])==1){//这个位置某数已经待过了,所以不考虑了
                continue;
            }
            
                
            swap(nums[i],nums[index]);
            backsee(n,res,nums,index+1,used);//问题缩小到第二个数
            swap(nums[i],nums[index]);
            ex[nums[i]]=1;
        }
        
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        int used[nums.size()];
        memset(used,0,sizeof(used));
        sort(nums.begin(),nums.end());
        backsee(nums.size(),res,nums,0,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
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这个问题类似于下面的目标和、部分和问题。

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :13.1 MB, 在所有 C++ 提交中击败了7.49%的用户

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 sousuo(vector<vector<int>>& res,vector<int>& nums,int index){
        if(index==nums.size()){
            res.push_back(nums);
            return;
        }
            
        int tmp=nums[index];
        //该元素不在
        nums.erase(nums.begin()+index);        
        sousuo(res,nums,index);
        //该元素在
        nums.insert(nums.begin()+index,tmp);
        sousuo(res,nums,index+1);
        
        
        
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        //想了一下方法 dfs  动态规划
        vector<vector<int>> res;
        // res.push_back(nums);
        sousuo(res,nums,0);
        return res;
        
    }
};

部分和&&目标和问题

部分和问题

这一段来自《挑战程序设计语言（第二版）》

给定整数a1、a2、…….an，判断是否可以从中选出若干数，使它们的和恰好为K。

1580957138(1).png)

样例输入：

1
2
3
n=4
a={1,2,4,7}
k=13

样例输出

1
Yes {13=2+4+7}

样例输入：

1
2
3
n=4
a={1,2,4,7}
k=15

样例输出

1
No

题解思路：从$a_1$开始按顺序决定每个数加或者不加，在全部n个数后判断它们的和是不是k即可。

状态数是$2^{n+1}$所以复杂度是O($2^n$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[MAX_N];
int n,k;

//已经从前i项得到了和sum，然后对于i项之后进行分支。
bool dfs(int i,int sum){
    //如果前n项都计算过了，则返回sum是否与k相等
    if(i==n)  return sum==k;
    //不加上a[i]的情况
    if(dfs(i+1,sum)) return ture;
    
    //加上a[i]的情况
    if(dfs(i+1,sum+a[i])) return true;
    return false;
}

void solve(){
    if (dfs(0,0)) printf("Yes\n");
    else printf("No\n");
}

目标和问题[动态规划等解法待补充]

类似问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一种类似暴力的解法

执行用时 :1776 ms, 在所有 C++ 提交中击败了8.70%的用户

内存消耗 :8.8 MB, 在所有 C++ 提交中击败了29.83%的用户

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:
    int jieguo(vector<int>& nums, int S,int now,int index,int count){
        if(index==nums.size()){
            if(now==S)
                return count+=1;
            else
                return count;
        }
        int res=0;
        res=jieguo(nums,S,now+nums[index],index+1,count);
        res=jieguo(nums,S,now-nums[index],index+1,res);
        return res;
        
    }
    
    int findTargetSumWays(vector<int>& nums, int S) {
        //用dfs方法
        int res=jieguo(nums,S,0,0,0);
        return res;
    }
};