# Backtracking

April 01, 2021

## Subsets

78. Subsets

medium | Accept. 80% | 力扣中文站

Given an integer array nums of unique elements, return all possible subsets.

Example:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
fun subsets(nums: IntArray): List<List<Int>> {
val ret = mutableListOf<List<Int>>()
val list = mutableListOf<Int>()

fun dfs(i: Int) {
// i also corresponds with the current level
// of the search tree.
if (i == nums.size) {
// We've gotton to bottom of the search tree.
// Report the answer by first creating a copy.
return
}

// We make the choice of taking the current element.
dfs(i + 1)

// Backtrack: undo the previous choice
list.removeAt(list.size - 1)    dfs(i + 1)
}

dfs(0)
return ret
}

Notice the two recursive calls in the dfs procedure correspond with the two branches on each level of the decision tree.

## Permutations

fun permute(nums: IntArray): List<List<Int>> {
val ret = mutableListOf<List<Int>>()
val list = mutableListOf<Int>()

fun dfs() {
if (list.size == nums.size) {
ret += list.toList()
return
}
for (n in nums) {
if (n in list) continue
list += n
dfs()
list.removeAt(list.size - 1)    }
}

dfs()
return ret
}

I usually stick with Java for LeetCode solutions. Recently, I feel Kotlin also shines in this area. For example, Java solutions of these backtracking problems require either storing some of the inputs in class fields, which, IMO, is poor programming style, or passing a long list of arguments to the dfs method, which obscures the algorithm a bit. With Kotlin, the code is concise and full of substance without being as gimmicky as Python.

## References

• Skiena, Steven S.. “Chapter 9. Combinatorial Search.” The Algorithm Design Manual. Switzerland, Springer International Publishing, 2020.