給定一個 沒有重復 數(shù)字的序列，返回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutations
著作權(quán)歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

算法

swift

參考鏈接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

// 結(jié)果集合
var result = [[Int]]()

func permute(_ nums: [Int]) -> [[Int]] {
    let length = nums.count
    // 過濾邊界值
    if length == 0 {
        return result
    }
    // 標記是否訪問過的數(shù)組
    let used = [Bool](repeating: false, count: length)
    // 訪問路徑
    let path = [Int]()
    dfs(nums, length, 0, path, used)
    return result
}

/// 深度優(yōu)先
/// - Parameters:
///   - nums: 原始數(shù)組
///   - length: 原始數(shù)組長度
///   - depth: 深度優(yōu)先遞歸深度
///   - path: 訪問路徑數(shù)組
///   - used: 訪問標記位數(shù)組
func dfs(_ nums: [Int], _ length: Int, _ depth: Int, _ path: [Int], _ used: [Bool]) {
    // 遞歸終結(jié)條件，路徑長度等于數(shù)組長度，本次遞歸結(jié)束，路徑添加到結(jié)果集中
    if length == depth {
        result.append(path)
        return
    }
    // 遞歸邏輯
    for i in 0..<length {
        // 未訪問過
        if !used[i] {
            // 每次嘗試都使用新的 路徑 和 訪問標記位，如果使用path和used需要回溯
            // 訪問的路徑添加到路徑之中
            var newPath = path
            newPath.append(nums[i])
            // 標記為已訪問
            var newUsed = used
            newUsed[i] = true
            dfs(nums, length, depth+1, newPath, newUsed)
        }
    }
}

• Java

// @lc code=start
class Solution {
    // 結(jié)果集
    List<List<Integer>> result;
    public List<List<Integer>> permute(int[] nums) {
        result = new ArrayList();
        // 過濾邊界條件
        if (nums.length == 0) {
            return result;
        }
        // 訪問的路徑
        List<Integer> path = new ArrayList<>();
        // 標記被訪問數(shù)組
        boolean[] used = new boolean[nums.length];
        dfs(nums, nums.length, 0, path, used);
        return result;
    }

    public void dfs(int[] nums, int length, int depth, List<Integer> path, boolean[] used) {
        // 遞歸終結(jié)條件
        if (depth == length){
            result.add(path);
            return;
        }
        // 遞歸邏輯
        for (int i = 0; i < nums.length; i++) {
            // 未被使用
            if (!used[i]) {
                // 新建 路徑數(shù)組 和 已訪問數(shù)組 保存當前的狀態(tài)
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(nums[i]);

                boolean[] newUsed = Arrays.copyOf(used, length);                
                newUsed[i] = true;
                // 下一層遞歸
                dfs(nums, nums.length, depth+1, newPath, newUsed);
            }
        }
    }
}

GitHub：https://github.com/huxq-coder/LeetCode
歡迎star