46.全排列

題目

題解

數(shù)組的全排列，其實(shí)就是當(dāng)前數(shù)字和剩余數(shù)字的全排列匯總結(jié)果。

以示例中的[1,2,3]舉例，可以進(jìn)行拆分為以下三個(gè)的結(jié)果集。

1?+?[2,3]
2?+?[1,3]
3?+?[1,2]

然后子集又可以再次進(jìn)行拆分，只需要進(jìn)行遞歸即可。

遞歸終止條件是什么？

很顯然，當(dāng)數(shù)組只有一個(gè)時(shí)，就意味著不會(huì)再有其他的排列情況了，直接放入結(jié)果集即可。

class?Solution?{
????public?List>?permute(int[]?nums)?{

????????List>?res?=?new?LinkedList<>();
????????List?record?=?new?LinkedList<>();
????????permute(res,?record,?nums);
????????return?res;
????}

????public?void?permute(List>?res?,List?record,?int[]?nums)?{

????????if?(nums.length?==?1)?{
????????????record.add(nums[0]);
????????????res.add(record);
????????????return;
????????}

????????for?(int?i?=?0;?i?????????????int[]?ints?=?removeIndex(nums,?i);
????????????LinkedList?list?=?new?LinkedList<>(record);
????????????list.add(nums[i]);
????????????permute(res,?list,?ints);
????????}

????}

????public?int[]?removeIndex(int[]?nums,?int?index)?{

????????int[]?ints?=?new?int[nums.length?-?1];

????????System.arraycopy(nums,?0,?ints,?0,?index);
????????System.arraycopy(nums,?index?+?1,?ints,?index,?nums.length?-?index?-?1);

????????return?ints;
????}

}

- -