What is Backtracking

An algorithm for exploring combinations that satisfy specified constraints.

It can be used to explore all unique combinations (nCr).

Implementation

Source code is as follows.

The process retrieves N unique subsequences from a given array. Below is an example of 4C3.

The recursive process can feel overwhelming, but thinking of the data as a tree structure makes it easier to understand.

When data consisting of 1, 2, 3, 4 is provided, consider what results are obtained for k values ranging from 0 to 4.

In short, k represents the depth of the tree structure, and the 3 in 4C3 can be considered as the depth.

Attempting to solve combinations without backtracking would result in nested loops of for statements.

One approach to write this efficiently using recursion is backtracking.

leetcode.com - subsets is a problem with multiple solutions, one of which can be solved using backtracking.