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

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

正常处理 - 添加下一个数字，直到达到限制。

Adding: 1

Adding: 2

Adding: 3

我们达到了上限，记录了1,2,3烫发并回溯，删除了3

Removing: 3

我们退出 backtrack(3) 调用，因为我们刚刚添加 2 我们立即将其删除。

Removing: 2

我们现在 继续添加 2 的循环并尝试 3 在 second 位置。

Adding: 3

列表现在包含 1,3。

我们现在循环查找第三个条目，发现 2 还不在列表中。

Adding: 2

它将 1,3,2 添加到结果列表中。

平衡去除2.

Removing: 2

等等

Answer 2

好吧，我会试着解释一下

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);
      }
   }
}

你开始你的 backTracking，每个选项卡都有不同的递归级别，每个级别都有你自己的局部变量（在本例中 'i'）

backtracking([empty list],[],[1,2,3])
   start for i = 0
   add to temp list nums[0] = 1
   call backtracking
   backtracking([],[1],[1,2,3])
      start for i = 0 // the other for it's waiting
      if(tempList.contains(nums[i])) //its true, then not add nums[0]
      now for i = 1
      add to temp list nums[1] = 2
      call backtracking
      backtracking([],[1,2],[1,2,3])
          start for i = 0 // the other two 'for' waiting
          if(tempList.contains(nums[i]))// true for nums[0],nums[1]
          now for i = 2
          add to temp list nums[2] = 3
          call backtracking
          backtracking([],[1,2,3],[1,2,3])
              if(tempList.size() == nums.length)//it's true
              //we have one permutation [1,2,3]
              //add templist in list
              finish this level of recursion, return to last level
          now for i = 3 then end recursion and remove
          tempList.remove(tempList.size() - 1);//after this templist = [1,2]
      now here the important part!!
      here remove again
      tempList.remove(tempList.size() - 1); // after this templist = [1]

      now i = 2 //see in this level before i = 1
      then the for continue
      add to temp list nums[2] = 3
      tempList = [1,3]//see that you first add 3 before delete 1
      call backtracking
      backtracking([],[1,3],[1,2,3])
          repeat process...
          here only we can add nums[1]
          add to temp list nums[1] = 2
          tempList = [1,3,2]
          call backtracking
          backtracking([],[1,3,2],[1,2,3])
              if(tempList.size() == nums.length)//it's true
              //we have other permutation [1,3,2]
              finish this level of recursion, return to last level
          i = 3 then end and delete '2' number
      i = 3 then end and delete '3' number
   now i = 2 // see this is the first recursion and templist = []
   add to temp list nums[1] = 2
   call backtracking
      backtracking([],[2,],[1,2,3]) // and you can continues the recursion.

我推荐在netbeans或eclipse中使用debug，你可以看到递归的每一层，看看它是如何工作的。

Answer 3

您的逻辑似乎有问题，因为在列表中添加 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;
}

如果需要，您可以收集所有排列组合以供进一步使用。

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

Generating permutations of the input sequence using backtracking

java

algorithm

backtracking