Two Sum

Subsets is the canonical introduction to the concept of backtracking.

While this problem can be solved without backtracking via iteration, the backtracking solution introduces the basic algorithm structure that will be expanded on in future, more complicated problems like Subsets II and Permutations.

Two Sum
Solved
Easy
Topics
Companies
Hint
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
 

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Solution

The backtracking-based function uses backtracking to progressively explore the solution set. The key insight is the creation and maintenance of the current subset, which is added to, and then removed from, as the traversal takes place across the solution space.

func twoSum(nums []int, target int) []int {
  seen := make(map[int]int) // number -> index

  for i, num := range nums { // traverse nums
    compliment := target - num // compliment is the remainder

    if j, ok := seen[compliment]; ok { // if compliment found, return
        return []int{i, j}
    }

    seen[num] = i // compliment not found, store num at i
  }

  return nil // not covered by test cases but good practice
}

Breakdown: