[leetcode]46. Permutations 전체 정렬(일반 시퀀스에 중복 요소 없음)

4516 단어
Given a collection of distinct integers, return all possible permutations.
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

 
제목:
전체 정렬 인쇄
 
Solution1: Backtracking
형식화된 표현 귀속 과정:permutations(nums[0...n-1]) = {숫자를 꺼내라}+permutations(nums[0...n-1] - 이 숫자)
 
code
 1 /*
 2 Time: O(n!)
 3 Space: O(n!). We allocate space to keep N! paths.
 4 */
 5 
 6 
 7 class Solution {
 8     public List> permute(int[] nums) {
 9         List> result = new ArrayList<>();
10         // corner case
11         if (nums == null || nums.length == 0) return result;
12         List path = new ArrayList<>();
13         helper(nums, path, result);
14         return result; 
15     }
16     
17     private void helper(int[] nums, List path, List> result){
18         // base case
19         if(path.size() == nums.length){
20             result.add(new ArrayList<>(path));
21             return;
22         }
23         
24         for(int i = 0; i< nums.length; i++){
25             if(path.contains(nums[i])) continue;
26             path.add(nums[i]);
27             helper(nums, path, result);
28             path.remove(path.size() - 1);
29         }
30     }
31 }

 
다음으로 전송:https://www.cnblogs.com/liuliu5151/p/9201935.html

좋은 웹페이지 즐겨찾기