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.
Contains Duplicate
Solved
Easy
Topics
Companies
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
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 containsDuplicate(nums []int) bool {
seen := make(map[int]struct{}) // create int set
for _, num := range nums { // traverse nums
if _, ok := seen[num]; ok { // if num was seen, return true
return true
}
seen[num] = struct{}{} // map set
}
return false // every num was distinct
}
Breakdown: