The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# Problem statement
**Given a string, find out all its subsequences.**

> A string is a subsequence of a given string that is generated by deleting some character of a given string without changing its order.

For example, if you have an input string as `abc`, the subsequences of this string can be `a`, `b`, `c`, `ab`, `ac`, `bc`, `abc`.

# Solution: **Recursive approach**
One by one, fix characters and recursively generate all subsets starting from them. After every recursive call, we remove the last character so that the next permutation can be generated. Let's now move on to the implementation now.

#include <iostream>
using namespace std;

void subsequences(char *input, char *output, int i, int j){
    if(input[i] == '\0'){
        output[j] = '\0';
        cout<<output<<endl;
        return;
    }
    output[j] = input[i];
    subsequences(input,output,i+1,j+1);

    subsequences(input,output,i+1,j);
}

int main() {
    char input[] = {'a','b','c','\0'};
    char output[100];
    subsequences(input,output,0,0);
    return 0;
}


**Explanation:**

* On line 4, we define our function `subsequences()`, which will accept the input string in the form of character array `input` (you can use strings also), the output character array `output`, and the starting and ending index for the string as `i` and `j` respectively.
* From lines 5 to 8, we check if we reached the character `\0`, which is the terminating character for every string. Then, we can print the string.
* On line 10, we are passing the ${i^{th}}$ input to the ${j^{th}}$ output.
* On line 11, we call the function recursively and the ${1^{st}}$ character of the input string is considered in the output string.
* On line 13, we again call the function recursively by incrementing the value of `i` but not changing the value of `j` because in this case, we do not include the ${1^{st}}$ character of the input string to be printed in the output string.
* In the `main()` function, we define our input array and output array and then pass it to our function.

Learn how to print all the possible subsequences of a string using Recursion.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

All Possible Subsequences of a String

Problem statement