Combinations
A Backtracking Problem

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 rocksolid 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 reverseengineer 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 kth position of the combination can have only (n  k + 1) numbers.
Speaking in the terms of Backtracking, the candidates for the 1^{st} position of combination are all n numbers from 1 to n, 2^{nd} position can have (n  1) numbers which does not include the number present in the 1^{st} position of the combination. Moving forward in this way, candidates for the k^{th} 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 indepth 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:
 Letter Case Permutation
 Power Set
 All Paths Between Two Nodes
 Word Search
 Sudoku
 NQueens
 Word Square
 Generate Parentheses
The above content is written by:
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
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn