• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# LeetCode – Medium – 46. Permutations

2周前 (04-07) 7次浏览

• Backtracking

## Description

https://leetcode.com/problems/permutations/

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

``````Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
``````

Example 2:

``````Input: nums = [0,1]
Output: [[0,1],[1,0]]
``````

Example 3:

``````Input: nums = [1]
Output: [[1]]
``````

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

## Analysis

### 方法一：回溯算法（不使用startIndex）

#### 回溯三弄

##### 递归函数参数

``````private void backtracking(List<Integer> path, int[] nums, boolean[] used, List<List<Integer>> results) {}
``````
##### 递归终止条件

``````if (path.size() == nums.length) {
results.add(new ArrayList<>(path));
return;
}
``````
##### 单层搜索逻辑

``````for (int i = 0; i < nums.length; i++) {
if (used[i])
continue;

used[i] = true;
path.add(nums[i]);
backtracking(path, nums, used, results);
path.remove(path.size() - 1);
used[i] = false;
}
``````

### 参考资料

1. 回溯算法：排列问题！
2. 剑指Offer 2nd – 字符串的排列

## Submission

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

public class Permutations {

// 方法一：回溯算法
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtracking(path, nums, used, results);
return results;
}

private void backtracking(List<Integer> path, int[] nums, boolean[] used, List<List<Integer>> results) {
if (path.size() == nums.length) {
results.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i])
continue;

used[i] = true;
path.add(nums[i]);
backtracking(path, nums, used, results);
path.remove(path.size() - 1);
used[i] = false;
}
}

// 方法二：回溯算法2
public List<List<Integer>> permute2(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtracking2(path, 0, nums, results);
return results;
}

private void backtracking2(List<Integer> path, int startIndex, //
int[] array, List<List<Integer>> results) {

if (startIndex == array.length) {
results.add(new ArrayList<>(path));
return;
}

for (int i = startIndex; i < array.length; i++) {
swap(array, startIndex, i);
path.add(array[startIndex]);
backtracking2(path, startIndex + 1, array, results);
path.remove(path.size() - 1);
swap(array, startIndex, i);
}
}

private void swap(int[] num, int i, int j) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}

}

``````

## Test

``````import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.List;

import static org.hamcrest.collection.IsIterableContainingInAnyOrder.*;

import org.hamcrest.Matcher;
import org.junit.Test;

@SuppressWarnings("unchecked")
public class PermutationsTest {

private final Permutations obj = new Permutations();

private final int[] array = {1, 2, 3};
private final Matcher<Iterable<? extends List<Integer>>> expected = containsInAnyOrder(Arrays.asList(1, 2, 3), //
Arrays.asList(1, 3, 2), Arrays.asList(2, 1, 3), Arrays.asList(2, 3, 1),//
Arrays.asList(3, 1, 2), Arrays.asList(3, 2, 1));

private final int[] array2 = {0, 1};
private final Matcher<Iterable<? extends List<Integer>>> expected2 = containsInAnyOrder(Arrays.asList(0, 1), Arrays.asList(1, 0));

private final int[] array3 = {1};
private final Matcher<Iterable<? extends List<Integer>>> expected3 = containsInAnyOrder(Arrays.asList(1));

@Test
public void test() {
assertThat(obj.permute(array), expected);
assertThat(obj.permute(array2), expected2);
assertThat(obj.permute(array3), expected3);
}

@Test
public void test2() {
assertThat(obj.permute2(array), expected);
assertThat(obj.permute2(array2), expected2);
assertThat(obj.permute2(array3), expected3);
}
}
``````

© 著作权归作者所有

0

0 收藏

QQ

### 作者的其它热门文章

【清华大学】《逻辑学概论》笔记
《Java8实战》笔记（10）：用Optional取代null
Kafka学习笔记
Redis学习笔记