有人可以告诉我代码有什么问题吗？它没有打印数组的所有排列

Question

这是回溯的常见问题。这里我们必须打印数字数组的可能排列。 我写的代码：

import java.util.*;

public class Arraypermutations {
    public static void helper(List<List<Integer>> Array, List<Integer> permute, boolean done, List<Integer> nums){
         
        if (nums.size() == 0) {
            Array.add(new ArrayList<>(permute));
            return;
        }

        for(int i = 0; i < nums.size(); i++) {
            int currInt = nums.get(i);
            nums.remove(i);
            helper(Array, permute, permute.add(currInt), nums);
        }
    }

    public static List<List<Integer>> permute(int num[]){
        List<Integer> nums = new ArrayList<>();

        for (int i : num) {
            nums.add(i);
        }

        List<List<Integer>> Array = new ArrayList<>();
        List<Integer> permute = new ArrayList<>();
        boolean done = false;
        helper(Array, permute, done, nums);
        return Array;
    }

    public static void main(String[] args) {
        int num[] = {1,2,3};   
        List<List<Integer>> Array = permute(num);
        System.out.println(Array);
    }

}

这将是代码的预期答案。 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 但我的代码只给出 [[1,2,3]]； 作为答案。 问题出在代码的回溯中。 但我不太明白； 请帮忙！

Answer 1

试试这个

import java.util.*;
public class ArrayPermutations {
    public static void helper(List<List<Integer>> result, List<Integer> current, List<Integer> nums) {
        if (nums.size() == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            int currInt = nums.get(i);
            nums.remove(i);
            current.add(currInt);

            helper(result, current, nums);

            current.remove(current.size() - 1);  // Backtrack: remove the last added element
            nums.add(i, currInt);  // Backtrack: restore the removed element at its original position
        }
    }

    public static List<List<Integer>> permute(int num[]) {
        List<Integer> nums = new ArrayList<>();
        for (int i : num) {
            nums.add(i);
        }
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        helper(result, current, nums);
        return result;
    }

    public static void main(String[] args) {
        int num[] = {1, 2, 3};
        List<List<Integer>> result = permute(num);
        System.out.println(result);
    }
}

Answer 2

代码中的问题在于您在迭代 nums 列表时回溯和操作它的方式。当您在迭代期间从 nums 列表中删除一个元素时，它会影响剩余元素的索引，从而导致不正确的结果。

这是代码的更正版本：

import java.util.*;

public class ArrayPermutations {
    public static void helper(List<List<Integer>> result, List<Integer> permute, List<Integer> nums) {
        if (nums.size() == 0) {
            result.add(new ArrayList<>(permute));
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            int currInt = nums.get(i);
            permute.add(currInt);
            nums.remove(i);
            helper(result, permute, nums);
            nums.add(i, currInt);
            permute.remove(permute.size() - 1);
        }
    }

    public static List<List<Integer>> permute(int[] num) {
        List<Integer> nums = new ArrayList<>();
        for (int i : num) {
            nums.add(i);
        }
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> permute = new ArrayList<>();
        helper(result, permute, nums);
        return result;
    }

    public static void main(String[] args) {
        int[] num = {1, 2, 3};
        List<List<Integer>> result = permute(num);
        System.out.println(result);
    }
}

Answer 3

for (int i = 0; i < nums.size(); i++) {
    int currInt = nums.get(i);
    nums.remove(i);
    permute.add(currInt);
    helper(array, permute, nums);
    permute.remove(permute.size() - 1); 
    nums.add(i, currInt); 
}

请修改您的

for

循环，这可能有助于解决问题。