class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        for num in nums {
            let index = nums.index(of: num)!
            var newNums = nums
            newNums.remove(at: index)
            dfs(a: [num], b: newNums)
        }
        return [[1]]
    }

    func dfs(a: [Int], b:[Int]) {
        if b.count == 1 {
            print(a+b)
        }else {


            for index in 0 ..< b.count {
                var tmpA = a
                var tmpB = b

                let bElement = b[index]
                tmpA.append(bElement)
                tmpB.remove(at: index)

                dfs(a: tmpA, b: tmpB)
            }



            /*
            var firstNewA = a
            var firstNewB = b
            let b0 = firstNewB[0]
            firstNewA.append(b0)
            firstNewB.remove(at: 0)
            dfs(a: firstNewA, b: firstNewB)

            var secondNewA = a
            var secondNewB = b
            let b1 = secondNewB[1]
            secondNewA.append(b1)
            secondNewB.remove(at: 1)
            dfs(a: secondNewA, b: secondNewB)
            */
        }
    }
}

let sol = Solution()
sol.permute([1,2,3,4])