回溯法解决全排列问题,用java实现
时间: 2023-09-30 09:11:31 浏览: 135
好的,下面是用 Java 实现回溯法解决全排列问题的代码:
```java
import java.util.ArrayList;
import java.util.List;
public class Permutations {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, used, temp, result);
return result;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> temp, List<List<Integer>> result) {
if (temp.size() == nums.length) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
temp.add(nums[i]);
used[i] = true;
backtrack(nums, used, temp, result);
temp.remove(temp.size() - 1);
used[i] = false;
}
}
}
```
以上代码中,`permute` 方法是入口方法,接收一个整数数组,返回全排列的结果。在 `permute` 方法中,我们定义了一个布尔数组 `used` 来表示每个元素是否已经使用过,还定义了一个 `temp` 列表来存储每个排列的中间结果。然后调用 `backtrack` 方法来进行回溯。
在 `backtrack` 方法中,我们首先判断是否已经找到了一个完整的排列,如果是,就将当前的 `temp` 列表加入到 `result` 列表中。否则,我们遍历整个数组,对于每个元素,如果它已经使用过,就跳过;否则,将其添加到 `temp` 列表中,并将 `used` 数组中对应的值设置为 `true`,然后递归调用 `backtrack` 方法。在递归调用之后,我们需要将 `temp` 列表中的最后一个元素移除,并将 `used` 数组中对应的值设为 `false`,这样才能进行下一次回溯。
阅读全文
相关推荐


















