題目

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

Example:
Input: [1,2,3]
Output:

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

解法思路（一）

• 排列的問(wèn)題；
• 回溯法；
• 當(dāng)給出輸入的數(shù)組，代表整個(gè)排列組合的樹(shù)就已經(jīng)形成了，如下：

算法過(guò)程.png

• 問(wèn)題轉(zhuǎn)換成了，求這棵樹(shù)中，所有從根節(jié)點(diǎn)到空節(jié)點(diǎn)的路徑；

排列和組合的區(qū)別

• 排列的遞歸樹(shù)是這樣的：當(dāng)選中一個(gè)元素后，下一個(gè)元素只要不是這個(gè)元素就行；
• 組合的遞歸樹(shù)是這樣的：當(dāng)選中一個(gè)元素后，下一個(gè)元素只能是選中元素之后的元素；

解法實(shí)現(xiàn)（一）

關(guān)鍵字

回溯 遞歸 樹(shù) 樹(shù)的路徑 排列

實(shí)現(xiàn)細(xì)節(jié)

• 由于樹(shù)上每一層的邊是有沖突的，上層的邊用過(guò)的數(shù)字，下層的邊就不能再用了，所以在回溯的過(guò)程中，要將邊的狀態(tài)置為可用；
• 已經(jīng)確定的排列組合在往 res 中放的時(shí)候，要注意是深拷貝，否則遞歸過(guò)程中找到的組合保存不下來(lái)；
• 用一個(gè)輔助數(shù)組 used 記錄每個(gè)數(shù)字是否可選的狀態(tài)；

package leetcode._46;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution46_1 {

    private List<List<Integer>> res;
    private boolean[] used;

    public List<List<Integer>> permute(int[] nums) {

        res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return res;
        }

        used = new boolean[nums.length];
        LinkedList<Integer> combination = new LinkedList<>();

        findCombination(nums, 0, combination);

        return res;
    }

    private void findCombination(int[] nums, int index, LinkedList<Integer> combination) {

        if (index == nums.length) {
            res.add((List<Integer>)combination.clone());
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                combination.addLast(nums[i]);
                used[i] = true;
                findCombination(nums, index + 1, combination);
                combination.removeLast();
                used[i] = false;
            }
        }

        return;
    }

}

返回 LeetCode [Java] 目錄