Backtracking Leetcode questions and solutions in Swift
Question 1 - Subsets
Given an integer array nums of unique elements, return all possible subsets(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Solution:
class Solution {
func subsets(_ nums: [Int]) -> [[Int]] {
var ans = [[Int]]()
var curr : [Int] = []
func backtrack(_ curr : inout [Int], _ index : Int) {
if index > nums.count {
return
}
ans.append(curr)
for i in index..<nums.count {
curr.append(nums[i])
backtrack(&curr, i+1)
curr.removeLast()
}
}
backtrack(&curr,0)
return ans
}
}
Question 2 - Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Solution:
class Solution {
func permute(_ nums: [Int]) -> [[Int]] {
var ans = [[Int]]()
var curr : [Int] = []
func backtrack(_ curr : inout [Int]) {
if curr.count == nums.count {
ans.append(curr)
return
}
for num in nums {
if !curr.contains(num) {
curr.append(num)
backtrack(&curr)
curr.removeLast()
}
}
}
backtrack(&curr)
return ans
}
}
Question 3 - Combinations
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
Constraints**:**
1 <= n <= 201 <= k <= n
Solution:
class Solution {
func combine(_ n: Int, _ k: Int) -> [[Int]] {
var ans = [[Int]]()
var curr = [Int]()
func backtrack(_ curr : inout [Int] , _ index : Int) {
if curr.count == k {
ans.append(curr)
return
}
for i in index..<n+1 {
curr.append(i)
backtrack(&curr,i+1)
curr.removeLast()
}
}
backtrack(&curr,1)
return ans
}
}
Question 4 - Combination Sum 3
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers
1through9are used.Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
Example 2:
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
Example 3:
Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.
Constraints:
2 <= k <= 91 <= n <= 60
Solution:
class Solution {
func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
var ans = [[Int]]()
var curr = [Int]()
func backtrack(_ curr : inout [Int], _ index : Int) {
if curr.count == k {
if curr.reduce(0) { $0 + $1 } == n {
ans.append(curr)
}
return
}
for i in index..<10 {
if !curr.contains(i) {
curr.append(i)
backtrack(&curr, i+1)
curr.removeLast()
}
}
}
backtrack(&curr, 1)
return ans
}
}
Question 5 - Letter Combination of a phone number
Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Solution:
class Solution {
func letterCombinations(_ digits: String) -> [String] {
if digits.isEmpty {
return []
}
let answers: [Character: String] = ["2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"]
var result: [String] = []
var current: [Character] = []
func backtrack(_ index: Int) {
if index == digits.count {
result.append(String(current))
return
}
let digit = digits[digits.index(digits.startIndex, offsetBy: index)]
let letters = answers[digit]!
for letter in letters {
current.append(letter)
backtrack(index + 1)
current.removeLast()
}
}
backtrack(0)
return result
}
}
Question 6 - Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40All elements of
candidatesare distinct.1 <= target <= 40
Solution:
class Solution {
func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
var ans = [[Int]]()
var path = [Int]()
func backtrack(_ index : Int, _ sum : Int ) {
if sum == target {
ans.append(path)
return
}
for i in index..<candidates.count {
let num = candidates[i]
if sum + num <= target {
path.append(num)
backtrack(i,sum+num)
path.removeLast()
}
}
}
backtrack(0,0)
return ans
}
}
Question 7 - N-Queens III Problem
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [["Q"]]
Constraints:
1 <= n <= 9
Solution:
class Solution {
func totalNQueens(_ n: Int) -> Int {
var col = Set<Int>()
var diagonal = Set<Int>()
var antiDiagonal = Set<Int>()
func backtrack(_ row: Int, _ colSet: inout Set<Int>, _ diagonalSet: inout Set<Int>, _ antiDiagonalSet: inout Set<Int>) -> Int {
if row == n {
return 1
}
var ans = 0
for column in 0..<n {
let currDiagonal = row - column
let currAntiDiagonal = row + column
if colSet.contains(column) || diagonalSet.contains(currDiagonal) || antiDiagonalSet.contains(currAntiDiagonal) {
continue
}
colSet.insert(column)
diagonalSet.insert(currDiagonal)
antiDiagonalSet.insert(currAntiDiagonal)
ans += backtrack(row + 1, &colSet, &diagonalSet, &antiDiagonalSet)
colSet.remove(column)
diagonalSet.remove(currDiagonal)
antiDiagonalSet.remove(currAntiDiagonal)
}
return ans
}
return backtrack(0, &col, &diagonal, &antiDiagonal)
}
}