使用回溯生成给定数组的排列

Question

我正在尝试这个问题，我们需要找到数组中元素的排列。

这是leetcode problem no 46。我遇到的问题是我无法输出 ans 它只是不断返回空白 ArrayLists:

代码：

public List<List<Integer>> permute(int[] nums) 
{
    List<List<Integer>> fans = new ArrayList<>();
    HashMap<Integer, Integer> fmap = new HashMap<>();
    for(int i: nums){
        fmap.put(i, fmap.getOrDefault(i, 0) + 1);
    }
    int n=nums.length;
    List<Integer> ans=new ArrayList<>(n);
    dfs(1, n, fmap, ans, fans);
    return fans;
}

public void dfs(int cs, int ts, HashMap<Integer, Integer> fmap,List<Integer> ans, List<List<Integer>> fans)
{    
    if (cs > ts)
    {
        fans.add(ans);
        return;
    }
    for(Integer val: fmap.keySet())
    {
        if (fmap.get(val) > 0)
        {
            fmap.put(val, fmap.get(val) - 1);
            ans.add(val);
            dfs(cs + 1, ts, fmap, ans, fans);
            ans.remove(ans.size() - 1);
            fmap.put(val, fmap.get(val) + 1);
        } 
    }  
}

测试用例的输出 [0,1]:

[[],[]]

实际输出应该是：

[[0,1],[1,0]]

当我在递归方法中检查“潜在答案”时，我能够看到正确答案。我的意思是，如果我在 dfs 方法中打印输出，它会显示正确答案：

代码更改：

 if (cs > ts)
    {
        fans.add(ans);
        System.out.println(fans);
        return;
    }

现在正在打印 fans:

的值

[[0, 1]]
[[1, 0], [1, 0]]

但是这些值没有在 fans 中更新，返回的值变为空白。

我读到有人提到了同样的问题，但它是针对 Python 的，在这种情况下的解决方案是对列表进行深度复制。

我不知道如何在 Java 中做到这一点。

我做错了什么？

Answer 1

为了生成排列列表，您不需要 Map。您只引入了多余的操作，这些操作无论如何都没有用。如果您有疑问，请添加几个 print-statements 以可视化地图状态，它将始终包含具有相同值 1 的相同键（输入中的所有数字保证是唯一的）并且它没有影响关于结果。

生成排列的数据来源

除了尝试利用 HashMap 作为生成排列的数据源由于错误而无法正常工作之外，这也不是一个好主意，因为 [=82 的顺序迭代=]keySet of HashMap 不保证一致。

作为存储当前排列中尚未应用的数字的统一平均值，我们可以使用 ArrayList。在这种情况下，因为输入中不会有重复项（请参阅下面 leetcode 中的引述），我们可以使用 LinkedHashSet 来提高性能。如下所述，元素的删除将发生在每次递归调用之前，并且从 ArrayList 中删除的成本为 O(n)，同时 LinkedHashSet 它将减少到 O(1).

Constraints:

1 <= nums.length <= 6

-10 <= nums[i] <= 10

All the integers of nums are unique.

生成排列

每个生成的排列应该包含在它自己的列表 中。在您的代码中，您创建了一个列表，该列表在递归调用期间传递，最终每个递归分支都会将相同的列表添加到结果列表中。这显然不应该发生。

你看，结果打印为 [[],[]]。看起来像是一个包含两个列表的列表，但实际上它们指的是同一个空列表。

并且此列表为空，因为添加到其中的每个元素在执行递归调用后都将被删除：

ans.add(val);
... <- rursive call in between
ans.remove(ans.size() - 1); // removes the last element

if I print the output in the dfs method, it shows the correct answer:

实际上，这是不正确的。如果仔细查看结果，您会发现嵌套列表是相同的 [[1, 0], [1, 0]].

最终结果为空，因为所有递归调用都发生在添加和删除的每个值之间（参见上面的代码片段）。 IE。移除将按照尊崇的顺序进行。那将是要执行的最后几行，而不是 return 语句。为了更好地理解它，我建议您逐行浏览代码，并在纸上画出对 ans 列表所做的所有更改，以获得像 [0, 1].

这样的简单输入

相反，您应该创建包含未完全生成的排列 (answer) 的列表的副本，然后添加一个元素进入copy。这样初始的排列（answer）不受影响，可以在所有后续迭代中用作模板。

List<Integer> updatedAnswer = new ArrayList<>(answer);
updatedAnswer.add(next);

并且你还需要创建一个copy数据源并移除添加到新创建的permutation的元素（answer) 以避免重复此元素：

Set<Integer> updatedSource = new LinkedHashSet<>(source);
updatedSource.remove(next);

旁注：为方法和变量赋予有意义的名称是一种很好的做法。例如，名称 cs 和 ts 没有提供信息（不看代码就不清楚它们要存储什么），method-name dfs 令人困惑，DFS是一个well-known算法，用于遍历树或图数据结构，但与本题无关

构建递归解决方案

将递归方法保持为 void 是有意义的，以避免用一个额外的列表包装结果，该列表随后会被丢弃，但通常 return 结果更方便而不是在参数中累积它。出于性能原因，我将方法保留为 void.

每个递归实现都应该包含两部分：

基本案例 - 代表一个简单的 edge-case（或一组 edge-case），其结果是预先知道的。对于这个问题，base case 将表示给定 permutation 已达到初始数组大小时的情况，即源将不包含任何元素，我们需要检查它是否为空。问题中提供的解决方案中用于此检查的参数 cs 和 ts 是多余的。
递归案例 - 解决方案的一部分，其中递归调用已完成并且主要逻辑所在。在 递归情况 中，我们需要复制给定的答案和来源，如上文所述，并将更新后的副本用作每个递归调用的参数。

这可能是这样实现的：

public static List<List<Integer>> permute(int[] nums) {
    Set<Integer> source = new LinkedHashSet<>();
    for (int next: nums) source.add(next);
    
    List<List<Integer>> result = new ArrayList<>();
    permute(source, new ArrayList<>(), result);
    return result;
}

public static void permute(Set<Integer> source, List<Integer> answer,
                           List<List<Integer>> result) {
    
    if (source.isEmpty()) {
        result.add(answer);
        return;
    }
    
    for (Integer next: source) {
        List<Integer> updatedAnswer = new ArrayList<>(answer);
        updatedAnswer.add(next);
        Set<Integer> updatedSource = new LinkedHashSet<>(source);
        updatedSource.remove(next);
        permute(updatedSource, updatedAnswer, result);
    }
}

main()

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

输出：

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

A link to Online Demo

使用回溯生成给定数组的排列

Generating Permutations of the given array using Backtracking

java

algorithm

recursion

arraylist

backtracking

生成排列的数据来源

生成排列

构建递归解决方案