LeetCode047全排列II
题目:
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
java:
public class Leetcode047 { public static List<List<Integer>> res = new ArrayList<>(); public static List<Integer> path = new ArrayList<>(); public static List<List<Integer>> permute(int[] nums) { boolean[] used = new boolean[nums.length]; Arrays.fill(used, false); Arrays.sort(nums); backtrack(nums, used); return res; } private static void backtrack(int[] nums, boolean[] used) { if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; } if (used[i] == false) { used[i] = true; path.add(nums[i]); backtrack(nums, used); path.remove(path.size() - 1); used[i] = false; } } } public static void main(String[] args) { int[] nums = {1, 2, 3}; System.out.println(permute(nums)); } }Go:
package LeetCode import "sort" var ( res047 [][]int path047 []int st047 []bool ) func PermuteUnique047(nums []int) [][]int { res047 = make([][]int, 0) path047 = make([]int, len(nums)) st047 = make([]bool, len(nums)) sort.Ints(nums) dfs047(nums, 0) return res047 } func dfs047(nums []int, index int) { if index == len(nums) { tmp := make([]int, len(nums)) copy(tmp, nums) res047 = append(res047, tmp) } for i := 0; i < len(nums); i++ { if i != 0 && nums[i] == nums[i-1] && !st047[i-1] { continue } if !st047[i] { path047 = append(path047, nums[i]) st047[i] = true dfs047(nums, index+1) st047[i] = false path047 = path047[:len(path047)-1] } } } func main() { nums := []int{1, 1, 2} path := LeetCode.PermuteUnique047(nums) fmt.Println(path) }是否还会记着我的样子.
如果大家喜欢我的分享的话.可以关注我的微信公众号
念何架构之路