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

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语句向我展示了如何添加和删除数字(以及由此产生的排列)：

加:1 加:2 加:3 移除:3 移除:2 加:3 加:2 移除:2 移除:3 移除:1 加:2 加:1 加:3 移除:3 移除:1 加:3 加:1 移除:1 移除:3 移除:2 加:3 加:1 加:2 移除:2 移除:1 加:2 加:1 移除:1 移除:2 移除:3

虽然我理解它是如何添加和删除数字的，但我不知道它为什么会这样工作。根据我的理解，在生成第一个置换<1,2,3>之后，所有这三个数字都应该被删除。但事实并非如此。只有<2,3>被删除，留下了1。为什么会这样呢？我很感谢你的帮助。

Answer 1

正常处理-添加下一个号码，直到我们达到极限。

加:1 加:2 加:3

我们撞到天花板，记录1,2,3烫发和倒车，移除3。

移除:3

我们退出backtrack(3)调用，当我们刚刚添加2时，我们立即删除它。

移除:2

我们现在继续添加2 的循环，并在第二个位置尝试。

加:3

列表现在包含1,3。

我们现在循环第三个条目，并发现2还没有在列表中。

加:2

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

平衡去除2。

移除:2

等。

Answer 2

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

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

Answer 3

好吧，我试着解释一下

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中使用调试，您可以看到每个级别的递归，并查看它的工作方式。