java - 使用回溯生成输入序列的排列

Question

我正在练习 Leetcode 面试，其中一个问题是:

给定一个数字数组，您需要生成所有可能的排列。为了更好地理解，我转向了解决方案，其中一个是这样的:

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
       List<List<Integer>> list = new ArrayList<>();
       // Arrays.sort(nums); // not necessary
       backtrack(list, new ArrayList<>(), nums);
       return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
       if(tempList.size() == nums.length){
          list.add(new ArrayList<>(tempList));
       } else{
          for(int i = 0; i < nums.length; i++){ 
             if(tempList.contains(nums[i])) 
                 continue;
             System.out.println("Adding: "+nums[i]);
             tempList.add(nums[i]);
             backtrack(list, tempList, nums);
             System.out.println("Removing: "+nums[i]);
             tempList.remove(tempList.size() - 1);
          }
       }
    } 
}

两个print语句向我展示了如何添加和删除数字(以及因此生成的排列):

Adding: 1
Adding: 2
Adding: 3
Removing: 3
Removing: 2
--------> why is 1 not removed here?
Adding: 3
Adding: 2
Removing: 2
Removing: 3
Removing: 1
Adding: 2
Adding: 1
Adding: 3
Removing: 3
Removing: 1
Adding: 3
Adding: 1
Removing: 1
Removing: 3
Removing: 2
Adding: 3
Adding: 1
Adding: 2
Removing: 2
Removing: 1
Adding: 2
Adding: 1
Removing: 1
Removing: 2
Removing: 3

虽然我了解如何添加和删除数字，但我不确定为什么它以这种方式工作。据我了解，在生成第一个排列后 <1,2,3> , 所有这三个数字都应该被删除。但事实并非如此。只有<2,3>被移除，留下1在后面。为什么会这样？如果有任何帮助，我将不胜感激。

Answer 1

您的逻辑似乎有问题，因为在列表中添加 1、2、3 之后，您仅根据递归回溯两次，因此 1 将始终是您列表的一部分。

In Backtracking,
1
1->2
1->2->3
Remove 3 as no further element
Remove 2 from temp list but after this permute 2,3 ->3,2 
There is no need to remove all elements in single iteration over all elements, 
you can try with 4 input [1,2,3,4], will be more clear as many permutations will be 
there after removal of 2 as 2->3->4, 2->4->3. 

请在下面找到替代解决方案

public static void permutate() {
    int[] nums = new int[] { 1, 2, 3 };
    backTrack(nums, 0, nums.length - 1);
}

public static void backTrack(int[] str, int l, int r) {
   if (l == r) {
    System.out.print("\n");
    for (int ele : str) {
     System.out.print(ele);
    }
    } else {
        for (int i = l; i <= r; i++) {
            str = swap(str, l, i);
            backTrack(str, l + 1, r);
            str = swap(str, l, i);
        }
    }
}

public static int[] swap(int[] a, int i, int j) {
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
 return a;
}

如果需要，您可以收集所有排列是集合中的任何一个以供进一步使用。