全排列 ll (Permutations II)——回溯算法+dfs

梦里梦外; 2022-12-08 05:53 138阅读 0赞

# 全排列 ll——回溯算法 #

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

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

# 代码 #

package permutations_ii;
    
    import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution { 
    	boolean[] vis;
    
    	public List<List<Integer>> permuteUnique(int[] nums) { 
    		List<List<Integer>> ans = new ArrayList<List<Integer>>();
    		//使用 Deque是java官方statck类的建议
    		Deque<Integer> path = new ArrayDeque<Integer>();
    		vis = new boolean[nums.length];
    		Arrays.sort(nums);
    		backtrack(nums, ans, 0, path);
    		return ans;
    	}
    
    	public void backtrack(int[] nums, List<List<Integer>> ans, int idx, Deque<Integer> path) { 
    		if (idx == nums.length) { 
    			ans.add(new ArrayList<Integer>(path));
    			return;
    		}
    		for (int i = 0; i < nums.length; ++i) { 
    			if (vis[i]) { 
    				continue;
    			}
    			
    			// 剪枝条件, i > 0 是为了保证nums[i - 1]有意义
    			// vis[i - 1]是因为 vis[i - 1]在回退的过程中刚刚被撤销选择
    			if (i > 0 && nums[i] == nums[i - 1] && vis[i - 1] == false) { 
    				continue;
    			}
    			path.add(nums[i]);
    			vis[i] = true;
    			backtrack(nums, ans, idx + 1, path);
    			vis[i] = false;
    			path.removeLast();
    		}
    	}
    
    	public static void main(String[] args) { 
    		System.out.println(new Solution().permuteUnique(new int[] {  1, 1, 2 }));
    	}
    }

与[46题][46]，不同的是，序列中的数字可能是重复的。`for`循环里的判断  
可以简写成

if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) { 
                    continue;
                }

![在这里插入图片描述][20200918214740897.png]

[原题——47.全排列][47.]

[46]: https://blog.csdn.net/e891377/article/details/108464715
[20200918214740897.png]: /images/20221123/bbf1778437694a928b8ff529272eab1d.png
[47.]: https://leetcode-cn.com/problems/permutations-ii/