和《有重复数字的全排列》是一样的,有两种解法,第一种是使用选择和撤销,第二种是交换
解法1: 选择和撤销
每个位置的值都可以从所有的元素中选择,选择了当前位置的元素之后,再选下一个元素的,知道选完所有的值,得到一条结果
然后撤销,让当前位置选下一个元素,如此循环,知道该位置选了不同的元素
import java.util.*; public class Solution { ArrayList<String> result = new ArrayList<String>(); public ArrayList<String> Permutation(String str) { String[] input = str.split(""); LinkedList<String> item = new LinkedList<String>(); boolean[] visited = new boolean[input.length]; Arrays.sort(input); // 全排列可能会有重复 // 选择撤销 加一个数组visited permutate(input, item, visited); return result; } private void permutate(String[] input, LinkedList<String> item, boolean[] visited) { if (item.size() == input.length) { result.add(String.join("", item)); return; } for (int index = 0; index < input.length; index++) { // 不可以选的是,同一级里面,上一个一样的已经选择了,这个就不能再选了 if (visited[index] || index > 0 && visited[index - 1] == true && input[index - 1].equals(input[index]) ) { continue; } item.add(input[index]); visited[index] = true; permutate(input, item, visited); item.removeLast(); visited[index] = false; } } }
解法2:交换
每个位置都可以跟它后面的元素进行交换,其实也就是决定当前这个位置start是什么值
选中了start跟某个元素交换后
再对后面的元素也做交换,直到所有的位置都交换结束(终止条件)
然后再让它还原,start的位置再选择下一个元素
import java.util.*; public class Solution { Set<String> result = new HashSet<String>(); public ArrayList<String> Permutation(String str) { String[] input = str.split(""); permutate(0, input); return new ArrayList<String>(result); } private void permutate(int start, String[] input) { if (start == input.length - 1) { result.add(String.join("", input)); return; } for (int index = start; index < input.length; index++) { swap(input, start, index); permutate(start + 1, input); swap(input, start, index); } } private void swap(String[] input, int a, int b) { String temp = input[a]; input[a] = input[b]; input[b] = temp; } }