Backtracking

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.
      ret.add(list.toList())
      return
    }

    // We make the choice of taking the current element.
    list.add(nums[i])
    dfs(i + 1)

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

  dfs(0)
  return ret
}

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
}