參考實作: 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))