java - 试图找到整数数组元素的所有排列的集合

Question

在 main 方法中打印时，变量“result”为空。 有人可以指导我如何构建代码吗？ Java新手。如果问题很幼稚，我们深表歉意。

import java.util.ArrayList;
import java.util.List;

public class StringPermutation {

    public static void main(String[] args){
        int[] a = new int[]{1,2,3};
        System.out.println(permute(a)); 
    }

    public static List<List<Integer>> permute(int[] a) {        
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> result = new ArrayList(path);
        boolean[] visited = new boolean[a.length];
        helper(result, path, visited, a);
        //System.out.println(result);
        return result;
    }

    private static void helper(List<List<Integer>> result, List<Integer> path, boolean[] visited, int[] a) {
        if (path.size() == a.length)
            result.add(path);           

        for (int i = 0; i < a.length; i++) {
            if (visited[i]) continue;
            path.add(a[i]);
            visited[i] = true;
            helper(result, path, visited, a );
            path.remove(path.size() - 1);
            visited[i] = false;                     
        }                       
    }
}

Answer 1

您的问题是在每个递归调用中对 path 列表的引用。

当递归条件为 true 时，您必须克隆 path 列表或添加一个传递当前 path 列表的新列表:

//This constructor will create a new List adding the elements of `path`.
result.add(new ArrayList<>(path)); 

---

public class StringPermutation {

    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3};
        System.out.println(permute(a));
    }

    public static List<List<Integer>> permute(int[] a) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited = new boolean[a.length];
        helper(result, path, visited, a);
        //System.out.println(result);
        return result;
    }

    private static void helper(List<List<Integer>> result, List<Integer> path, boolean[] visited, int[] a) {
        if (path.size() == a.length)
            result.add(new ArrayList<>(path));

        for (int i = 0; i < a.length; i++) {
            if (visited[i]) continue;
            path.add(a[i]);
            visited[i] = true;
            helper(result, path, visited, a);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

调用主程序后，输出为:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]