✔[46]全排列（回溯） & ✔[47]全排列 II

深藏阁楼爱情的钟 2021-06-10 20:39 421阅读 0赞

回溯模板：

result = []
    def backtrack(路径, 选择列表):
        if 满足结束条件:
            result.add(路径)
            return
        
        for 选择 in 选择列表:
            做选择
            backtrack(路径, 选择列表)
            撤销选择

### ✔\[46\]全排列 ###

//给定一个 没有重复 数字的序列，返回其所有可能的全排列。  
//  
// 示例:  
// 输入: \[1,2,3\]  
//输出:  
//\[  
// \[1,2,3\],  
// \[1,3,2\],  
// \[2,1,3\],  
// \[2,3,1\],  
// \[3,1,2\],  
// \[3,2,1\]  
//\]  
// Related Topics 回溯算法  
采用常规的回溯算法，但是会包含1,1,1这些重复的，所以每次在加入的时候判断，原有数组中是否已经包含了该数字，是一种列出所有结果再过滤的方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70_pic_center]

import java.util.ArrayList;
    import java.util.List;
    class Solution { 
    	public List<List<Integer>> permute(int[] nums) { 
    		List<List<Integer>> res = new ArrayList<>();
    		// 边界检查
    		if (nums.length == 0) { 
    			return res;
    		}
    		dfs(nums, new ArrayList<>(), res);
    		return res;
    	}
    
    	private void dfs(int[] nums,List<Integer> combination, List<List<Integer>> res) { 
    		// 递归出口
    		if (combination.size() == nums.length) { 
    			res.add(new ArrayList<>(combination));
    			return;
    		}
    		// 对所有数字进行全排 再进行过滤
    		for (int i = 0; i < nums.length; i++) { 
    			if(!combination.contains(Integer.valueOf(nums[i]))) { 
    				combination.add(nums[i]);
    				dfs(nums, combination, res);
    				combination.remove(combination.size() - 1);
    			}
    		}
    	}
    }

解答成功:
    			执行耗时:3 ms,击败了46.69% 的Java用户
    			内存消耗:40.2 MB,击败了29.83% 的Java用户

嗯，问题是解决了。但不是很满意。。。  
看到网上别人写的，有一个是写了一个visited数组，来维护是否访问过，相比list的contains方法是更快的，因为数组按index访问是O(1)的，而list的contains方法是O(n),也是用空间换时间的一种方法。

import java.util.ArrayList;
    import java.util.List;
    class Solution { 
    	public List<List<Integer>> permute(int[] nums) { 
    
    		List<List<Integer>> res = new ArrayList<>();
    		// 维护一个已访问过的数组
    		int[] visited = new int[nums.length];
    		backtrack(res, nums, new ArrayList<Integer>(), visited);
    		return res;
    
    	}
    
    	private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) { 
    		if (tmp.size() == nums.length) { 
    			res.add(new ArrayList<>(tmp));
    			return;
    		}
    		for (int i = 0; i < nums.length; i++) { 
    			if (visited[i] == 1) continue;
    			visited[i] = 1;
    			tmp.add(nums[i]);
    			backtrack(res, nums, tmp, visited);
    			visited[i] = 0;
    			tmp.remove(tmp.size() - 1);
    		}
    	}
    }

解答成功:
    			执行耗时:2 ms,击败了82.95% 的Java用户
    			内存消耗:40.4 MB,击败了5.60% 的Java用户

不过空间复杂度是O(n)

### \[47\]全排列 II ###

//给定一个可包含重复数字的序列，返回所有不重复的全排列。  
//  
// 示例:  
// 输入: \[1,1,2\]  
//输出:  
//\[  
// \[1,1,2\],  
// \[1,2,1\],  
// \[2,1,1\]  
//\]  
// Related Topics 回溯算法

在前面的基础上，数字可以重复。  
1、用set暴力去重

import java.util.Arrays;
    import java.util.HashSet;
    import java.util.stream.Collectors;
    class Solution { 
    	public List<List<Integer>> permuteUnique(int[] nums) { 
    		int[] visited = new int[nums.length];
    		HashSet<List<Integer>> set = new HashSet();
    		backtrack(set, nums, new ArrayList<Integer>(), visited);
    		List<List<Integer>> res = new ArrayList<>(set);
    		return res;
    	}
    
    	private void backtrack(HashSet<List<Integer>> set, int[] nums, ArrayList<Integer> tmp, int[] visited) { 
    		if (tmp.size() == nums.length) { 
    			set.add(new ArrayList<>(tmp));
    			return;
    		}
    		for (int i = 0; i < nums.length; i++) { 
    			if (visited[i] == 1) continue;
    			visited[i] = 1;
    			tmp.add(nums[i]);
    			backtrack(set, nums, tmp, visited);
    			visited[i] = 0;
    			tmp.remove(tmp.size() - 1);
    		}
    	}
    }

解答成功:
    		执行耗时:36 ms,击败了14.54% 的Java用户
    		内存消耗:40.3 MB,击败了89.81% 的Java用户

2、排序+剪枝，在前一道题的基础上加上重复的剪枝

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    class Solution { 
    	public List<List<Integer>> permuteUnique(int[] nums) { 
    		List<List<Integer>> res = new ArrayList<>();
    		// 维护一个已访问过的数组
    		int[] visited = new int[nums.length];
    		// 排序，便于后面剪枝 ！！！加了这里
    		Arrays.sort(nums);
    		backtrack(res, nums, new ArrayList<Integer>(), visited);
    		return res;
    
    	}
    
    	private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) { 
    		if (tmp.size() == nums.length) { 
    			res.add(new ArrayList<>(tmp));
    			return;
    		}
    		for (int i = 0; i < nums.length; i++) { 
    			if (visited[i] == 1) continue;
    			// 如果数组相连元素相等，没有先访问后面的元素，就不会存在重复 ！！！加了这里
    			if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0){ 
    				continue;
    			}
    			visited[i] = 1;
    			tmp.add(nums[i]);
    			backtrack(res, nums, tmp, visited);
    			visited[i] = 0;
    			tmp.remove(tmp.size() - 1);
    		}
    	}
    }

解答成功:
    		执行耗时:1 ms,击败了100.00% 的Java用户
    		内存消耗:40.5 MB,击败了51.69% 的Java用户

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210518/27fc4d432c01494288ccb14fd3536c4d.png