Array Permutation/Combination by Iterative

參考實作: https://www.youtube.com/watch?v=zIY2BWdsbFs

Permutation:

func permutation(_ nums: [Int], _ n: Int) -> [[Int]] {
    var result: [[Int]] = []
    var cur: [Int] = []
    var used: [Bool] = Array(repeating: false, count: nums.count)
    helper(nums, &used, 0, n, 0, &cur, &result)
    return result
}


func helper(_ nums: [Int], _ used: inout [Bool], _ depth: Int, _ n: Int, _ startIndex: Int, _ cur: inout [Int], _ result: inout [[Int]]) {
    if depth == n {
        result.append(cur)
        return
    }
    
    for i in startIndex ..< nums.count {
        if !used[i] {
            used[i] = true
            cur.append(nums[i])
            helper(nums, &used, depth + 1, n, i + 1, &cur, &result)
            cur.removeLast()
            used[i] = false
        }
    }
}

print(permutation([1,2,3], 1))
print(permutation([1,2,3], 2))
print(permutation([1,2,3], 3))

Combination:

func combination(_ nums: [Int], _ n: Int) -> [[Int]] {
    var result: [[Int]] = []
    var cur: [Int] = []
    helper(nums, 0, n, 0, &cur, &result)
    return result
}


func helper(_ nums: [Int], _ depth: Int, _ n: Int, _ startIndex: Int, _ cur: inout [Int], _ result: inout [[Int]]) {
    if depth == n {
        result.append(cur)
        return
    }
    
    for i in startIndex ..< nums.count {
        cur.append(nums[i])
        helper(nums, depth + 1, n, i, &cur, &result)
        cur.removeLast()
    }
}

print(combination([1,2,3], 1))
print(combination([1,2,3], 2))
print(combination([1,2,3], 3))