LeetCode Trick

  • 6/2/2023
  • 2-minute read

In this summer, I spend a lot of time in doing LeetCode questions to improve my problem solving and software developing skills. However, it is normal for us to forget some questions that we have done. Therefore, in this post, I will make a summary about all tricks of approaching LeetCode questions that I have found. In general, I will include some templates, observations of solving a bunch of similar LeetCode questions.


Combination Questions

  • Input without duplication
    • Reuse of elements is not allowed
      • use a variable startIndex inside of the recursion function to label the first element to pick
      • call backTracking(.., .., i + 1), i + 1 is our startIndex of the next recursion
    • Reuse of elements is allowed
      • use a variable startIndex inside of the recursion function to label the first element to pick
      • call backTracking(.., .., i), i is our startIndex of the next recursion
  • Input with duplication
    • Reuse of elements is not allowed
      • Sort the input array
      • use a variable startIndex inside of the recursion function to label the first element to pick
      • call backTracking(.., .., i + 1), i + 1 is our startIndex of the next recursion
      • used array helps to skip duplicated elements in the same layer of the recursion tree

Subset Questions

  • Same as combination questions but need to collect outcome in each recursion function
  • My understanding: Combination questions are essentially subset questions with several constraints.

Permutation Questions

  • Input without duplication
    • Each recursion starts from picking the first element
    • used array helps to skip duplicated elements in the same path of the recursion tree
  • Input with duplication
    • Sort the input array
    • Each recursion starts from picking the first element
    • used array helps to skip duplicated elements in the same path and layer of the recursion tree

Knapsack Questions

  • 0-1 Knapsack Question (An object can only be added once)

    • 1D dynamic table:
      • Outer for loop - object and Inner for loop - knapsack capacity
    • Avoid an object being added to the knapsack multiple times

  • Multi Knapsack Question (An object can be added multiple times)

    • 1D dynamic table:
      • Outer for loop - object and Inner for loop - knapsack capacity: combination
      • Outer for loop - knapsack capacity and Inner for loop - object: permutation
AlgorithmLeetCode