java解决全排列问题

java解决全排列问题

全排列问题1

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

• 思路
  

   我们把问题看成n个排列成一行的空格，从左往右依次填入给定的n个数，每个数只能使用一次，可以使用回溯法。
递归函数backtrack(idx, perm)表示当前排列为perm，下一个待填入的位置是第idx个位置，下标从0开始。（1）假如idx == n，阐明填完了n个位置，找到了一个可行解，把perm放入效果数组中，递归结束；
（2）假如idx < n，必要思量第idx个位置填谁人数。使用标记数组visited来标记已经填过的元素，那么在填第idx个数的时间遍历给定的n个数，假如这个数没有被标记过，尝试填入，并将其标记，继续尝试下一个位置，调用backtrack(idx+1, perm)。搜索回溯时要打消该位置填的数以及标记，并尝试其他没被标记过的数。
（3）要解决重复问题，包管填第idx个数的时间重复数字只会被填入一次。我们选择对原数组排序，包管相同的数字都相邻，然后每次填入的数一定是这个数所在重复数聚集中从左往右第一个未被填过的数字。
  

• 示例
  

1. import java.util.ArrayList;
2. import java.util.Arrays;
3. import java.util.List;
5. public class Demo {
6.     public static void main(String[] args) {
7.         int[] nums = {1, 1, 2};
8.         Solution solution = new Solution();
9.         List<List<Integer>> lists = solution.permuteUnique(nums);
10.         System.out.println(lists);
11.     }
12. }
14. class Solution {
16.     boolean[] visited;
18.     public List<List<Integer>> permuteUnique(int[] nums) {
19.         List<List<Integer>> result = new ArrayList<>();
20.         visited = new boolean[nums.length];
21.         Arrays.sort(nums);
22.         List<Integer> perm = new ArrayList<>();
23.         backtrack(nums, result, 0, perm);
24.         return result;
25.     }
27.     private void backtrack(int[] nums, List<List<Integer>> result, int idx, List<Integer> perm) {
28.         if (idx == nums.length) {
29.             result.add(new ArrayList<>(perm));
30.             return;
31.         }
33.         for (int i=0;i<nums.length;i++) {
34.             if (visited[i] || (i > 0 && nums[i] == nums[i-1] && !visited[i-1]))
35.                 continue;
36.             perm.add(nums[i]);
37.             visited[i] = true;
38.             backtrack(nums, result, idx + 1, perm);
39.             visited[i] = false;
40.             perm.remove(idx);
41.         }
42.     }
43. }

复制代码

  [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
  全排列问题2

   给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以按任意顺序返回答案。

1. class Solution {
3.     boolean[] visited;
5.     public List<List<Integer>> permute(int[] nums) {
6.         List<List<Integer>> res = new ArrayList<>();
7.         visited = new boolean[nums.length];
8.         List<Integer> perm = new ArrayList<>();
9.         backtrace(res, nums, 0, perm);
10.         return res;
11.     }
13.     private void backtrace(List<List<Integer>> res, int[] nums, int idx, List<Integer> perm) {
14.         if (idx == nums.length) {
15.             res.add(new ArrayList<>(perm));
16.             return;
17.         }
19.         for (int i=0;i<nums.length;i++) {
20.             if (visited[i]) {
21.                 continue;
22.             }
24.             perm.add(nums[i]);
25.             visited[i] = true;
26.             backtrace(res, nums, idx+1, perm);
27.             visited[i] = false;
28.             perm.remove(idx);
29.         }
30.     }
31. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。