全排列——回溯算法+dfs

骑猪看日落 2022-12-04 15:56 162阅读 0赞

# leetcode.46.全排列——回溯算法+dfs #

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

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

# 思路 #

**回溯法** ：一种通过探索所有可能的**候选解**来找出**所有的解**的算法。如果**候选解**被确认不是一个解的话（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。  
![在这里插入图片描述][format_png_pic_center]

## java代码 ##

public List<List<Integer>> permute(int[] nums) { 
        	int len = nums.length;
        	List<List<Integer>> res = new ArrayList<>();
        	if(len ==0) { 
        		return res;
        	}
        	List<Integer> path = new ArrayList<>();
        	boolean[] used = new boolean[len];
        	dfs(nums,len,0,path,used,res);
        	return res;
    	}
    
        /** * * @param nums 数组 * @param len 数组长度,冗余变量 * @param depth 选了多少个 * @param path 路径 * @param used 已经选择的项 * @param res 结果集 */
    	private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) { 
    		if(depth == len) { 
    			res.add(new ArrayList<>(path));
    			return;
    		}
    		for(int i = 0;i<len;i++) { 
    			if(used[i]) { 
    				continue;
    			}
    			path.add(nums[i]);
    			used[i] = true;
    			
    			dfs(nums,len,depth+1,path,used,res);
                // 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
    			used[i] = false;
    			path.remove(path.size()-1);
    		}
    	}

### 不用标记数组 ###

class Solution { 
      public void backtrack(int n,
                            ArrayList<Integer> output,
                            List<List<Integer>> res,
                            int first) { 
        // 所有数都填完了
        if (first == n)
          res.add(new ArrayList<Integer>(output));
        for (int i = first; i < n; i++) { 
          // 动态维护数组
          Collections.swap(output, first, i);
          // 继续递归填下一个数
          backtrack(n, output, res, first + 1);
          // 撤销操作
          Collections.swap(output, first, i);
        }
      }
    
      public List<List<Integer>> permute(int[] nums) { 
        List<List<Integer>> res = new LinkedList();
    
        ArrayList<Integer> output = new ArrayList<Integer>();
        for (int num : nums)
          output.add(num);
    
        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
      }
    }

参考[permutations][]

## cpp代码 ##

//空间换时间，C++双100%代码
    class Solution { 
    public:
        vector<vector<int>> permute(vector<int>& nums) { 
            vector<vector<int>> res;
            if (nums.size() == 0) return res;        
            vector<int> temp;
            vector<int> used(nums.size(), 0); //空间换时间，记录当前数字是否用过
            int usedNum = 0;                  //记录多少个数字用过
            generate(res, nums, temp, used, 0);//深搜递归回溯
            return res;
        }
    
        void generate(vector<vector<int>>& res, vector<int>& nums, vector<int>& temp, vector<int>& used, int usedNum){ 
            //递归结束条件
            if (usedNum == nums.size()) { 
                res.push_back(temp);
                return;
            }
            //依次使用当前数字
            for (int i=0;i<nums.size();++i){ 
                //如果当前数字没有被使用，则使用
                if (used[i] == 0){ 
                    used[i] = 1;
                    temp.push_back(nums[i]);
                    //在当前位是当前数字的情况下，把所有的可能排列结果都找到并放入res；
                    generate(res, nums, temp, used, usedNum+1);
                    //当前位要换数字了，当前数字有可能出现在后面的位数里，所以开始回溯，清空状态量
                    used[i] = 0;
                    temp.pop_back();
                }
            }
            return;
        }
    };

# 参考资料 #

[liweiwei1419][]

[format_png_pic_center]: /images/20221123/2cb07403a3c54f23a6d170832b237d75.png
[permutations]: https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
[liweiwei1419]: https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/