Backtracking

How to use Backtracking in simple problems

When using backtracking we basically want to “take pictures” of a certain state of our list, object, etc. This “pictures” we save in another list and after we follow two paths. In the first one we increment something in that picture and in the second one we delete the element of that picture and start from the state before.

Example: I have a banana, apple and a chocolate and I want to try all the possible pictures.

1. No elements on the first scenario. We take an empty picture: []

2. We take a picture of our first element: [banana]

   1. We keep the banana and add the apple and now the picture is: [banana, apple]

   2. We keep the banana and the apple and add the chocolate and now the picture is: [banana, apple, chocolate]

   3. We remove the apple and now we have: [banana, chocolate]

   4. We remove the chocolate

3. We remove the banana and add the apple: [apple]

   1. We keep the apple and add the chocolate: [apple, chocolate]

4. We remove the apple and keep the chocolate [chocolate]

   1. ** Since chocolate is the last element of our list, we dont try any longer here.

In the end if we check our gallery we will have the following pictures: {[],[banana], [banana, apple], [banana, apple, chocolate] [banana, chocolate], [apple], [apple, chocolate], [chocolate]}

A simple code for a leet code challenge could be this one:

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var response = new List<IList<int>>();
        Backtrack(response, new List<int>(), nums, 0);
        return response;
    }

    public void Backtrack(IList<IList<int>> response, IList<int> current,int[] nums, int cont){
        response.Add(new List<int>(current)); // Here we add our current list to the final response;

        for(int i = cont; i < nums.Length; i++){
            current.Add(nums[i]); // Here we add the current element to the current list (banana or apple or chocolate)
            Backtrack(response, current, nums, i+1); // Here we backtrack keeping the item added before
            current.RemoveAt(current.Count - 1); /*Here we remove the item before and will try the next one 
                                                (Ex: remove banana and let's try with apple*/
        }
    }
}