网站规划与建设心得,大连网站建设报价,深圳松岗网站建设,云主机搭建网站LeetCode46.给定一个没有重复数字的序列#xff0c;返回其所有可能的全排列。例如#xff1a;
输入#xff1a;[1,2,3] 输出#xff1a;[[1,2,3]#xff0c;[1,3,2]#xff0c;[2,1,3]#xff0c;[2,3,1]#xff0c;[3,1,2]#xff0c;[3,2,1]]
元素1在[1,2]中已经使…LeetCode46.给定一个没有重复数字的序列返回其所有可能的全排列。例如
输入[1,2,3] 输出[[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]]
元素1在[1,2]中已经使用过了但是在[2,1]中还要再使用一次所以就不能使用startlndex了为此可以使用一个used数组来标记已经选择的元素
class Permute {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();boolean[] used;public ListListInteger permute(int[] nums) {if (nums.length 0) {return res;}used new boolean[nums.length];permuteHelper(nums);return res;}private void permuteHelper(int[] nums) {if (path.size() nums.length) {res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {if (used[i]) {continue;}used[i] true;path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] false;}}
}
在这里for循环中used[i]的变化可以这样理解现在这一层刚上来当前元素肯定是没有使用过的在执行了将used数组当前元素变为已使用将当前元素添加到path中后就要进入他的下一层了在他的下面几层当前元素都是使用过的。
