• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:


Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
You may return the answer in any order.

Example 1:
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]


Example 2:
Input: n = 1, k = 1
Output: [[1]]

Solution:


  • NOTE: I highly recommend going through the Backtracking chapters in the order they are given in the Index page to get the most out of it and be able to build a rock-solid understanding.


Writing algorithm for this problem is easy if you already know how to compute combinations manually using pen and paper. If you know how to find combinations manually, you just reverse-engineer the process to devise the algorithm.

If we are trying to find all possible combinations of size k out of n numbers from 1 to n, then the first position of the combination can have all n numbers, for each of these n numbers in the first position the second position can have (n - 1) numbers because we cannot include the number in a combination for second position which is already present in the first position. Proceeding in this way k-th position of the combination can have only (n - k + 1) numbers.

Speaking in the terms of Backtracking, the candidates for the 1st position of combination are all n numbers from 1 to n, 2nd position can have (n - 1) numbers which does not include the number present in the 1st position of the combination. Moving forward in this way, candidates for the kth position of a combination would be (n - k + 1) numbers not present in any of the previous (k - 1) positions in the current combination.

We will implement the above described algorithm using our Backtracking Template as follows:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Don't forget to take in-depth look at the other backtracking problems because that is what would make you comfortable with using the backtracking template and master the art of Backtracking:


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave