/
_0046_Permutations.java
70 lines (65 loc) · 2.08 KB
/
_0046_Permutations.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package com.diguage.algorithm.leetcode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
/**
* = 46. Permutations
*
* https://leetcode.com/problems/permutations/[Permutations - LeetCode]
*
* Given a collection of *distinct* integers, return all possible permutations.
*
* .Example:
* [source]
* ----
* Input: [1,2,3]
* Output:
* [
* [1,2,3],
* [1,3,2],
* [2,1,3],
* [2,3,1],
* [3,1,2],
* [3,2,1]
* ]
* ----
*
* @author D瓜哥, https://www.diguage.com/
* @since 2020-01-24 12:35
*/
public class _0046_Permutations {
/**
* Runtime: 5 ms, faster than 8.40% of Java online submissions for Permutations.
*
* Memory Usage: 45.3 MB, less than 5.68% of Java online submissions for Permutations.
*
* Copy from: https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)[A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partioning) - LeetCode Discuss]
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new LinkedList<>();
backtrack(nums, result, new ArrayList<Integer>());
return result;
}
private void backtrack(int[] nums, List<List<Integer>> result, ArrayList<Integer> path) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
} else {
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (path.contains(num)) {
continue;
}
path.add(num);
backtrack(nums, result, path);
path.remove(path.size() - 1);
}
}
}
public static void main(String[] args) {
_0046_Permutations solution = new _0046_Permutations();
int[] n1 = {1, 2, 3};
List<List<Integer>> r1 = solution.permute(n1);
System.out.println(Objects.toString(r1));
}
}