46. Permutations

xiaoxiao2021-02-28  9

Given a collection of distinct numbers, return all possible permutations.

For example, [1,2,3] have the following permutations:

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

題意:

給定一組每個元素都不同的數組,產生所有排列

題解: 使用回溯法,想像每一個數都是一個狀態 例如:[1,2,3],會有以下的排列 1.  1  2  3 2.  1,2  1,3  2,1  2,3  3,1  3,2 3.  1,2,3  1,3,2  2,1,3  2,3,1  3,1,2  3,2,1

package LeetCode.Medium; /* 使用回溯法,想像每一個數都是一個狀態 ex:123 1. 1 2 3 2. 1,2 1,3 2,1 2,3 3,1 3,2 3. 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 */ import java.util.ArrayList; import java.util.List; public class Permutations { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if(nums == null || nums.length == 0) return result; List<Integer> path = new ArrayList<Integer>(); dfs(path, result, nums); return result; } public void dfs(List<Integer> path, List<List<Integer>> result, int[] nums) { //若此組合的長度跟數組一樣,表示此數組已經組合完畢,則可以加入結果 if(path.size() == nums.length) { //為了防止path的結果歸零,故在 new 一個 List<Integer> complete = new ArrayList(path); result.add(complete); //此結果已經到頭了,結束 return; } //每次進行下一步時,都要從數組的第一個元素拜訪(因為排列位置都不一樣) for(int i = 0; i < nums.length; i ++) { //若當前組合包含此數字則略過 if(path.contains(nums[i])) { continue; } //將目前數字加入組合中 path.add(nums[i]); //歷遍下一個狀態 dfs(path, result, nums); //為了要保持此組合的當前狀態,故要將最後一個數刪除 path.remove(path.size() - 1); } } }

转载请注明原文地址: https://www.6miu.com/read-1100251.html

最新回复(0)