DEV Community: dhavalraj007

Override and New confusion in CSharp

dhavalraj007 — Sat, 31 Dec 2022 10:14:55 +0000

Try to read this answer from SO first https://stackoverflow.com/a/11046733/15225066
If you understand that. no need to read this article.

I will not provide the formal definitions and shit. If you want that go to MSDN.

Overview

Some Basics
Some Basics about "new" modifier
Example 1
Example 2 (do it yourself)

Some Basics

Objects can have different blueprint at runtime when using inheritance.
First thing You need to understand is that There is difference between object reference and the actual object.

    class Animal{/// Some code}
    class Cow : Animal{///Some code}

    static void Main()
    {
        Cow c = new Cow();
        // Note that we can also assign the Cow object to a Animal refrence
        Animal an = new Cow();
    }

(( Note that this new keyword is different. ))
new Cow() creates a object in heap returns its refrence(pointer or address of object in heap)
and we assign that to c variable which is refrence to a object of type of Cow.
Cow c, Animal an = Object reference
new Cow() = Actual Object

Main Point

The runtime blueprint(Methods and member vars) belongs to a "Actual Object" not to refrence. whereas the Access to Blueprint is determined by the Object reference. (read this line again this is very important)
meaning the Methods and member vars that the object has, gets decided when the object is created. and to access those methods we need the refrence which limits the access to those methods.

    class Animal
    {
        public virtual void Walk() { }
    }
    class Cow : Animal
    {
        public override void Walk() { }
        public void Milk() { }
    }

    static void Main()
    {
        Cow c = new Cow();

        // Note that I can also assign the Cow object to a Animal refrence
        Animal an = new Cow();
    }

Object
- new Cow()
- new Cow()
- both are same
methods in Object new Cow()
- void Cow.Milk()
- void Cow.Walk()
methods accesible with refrence Animal an = new Cow()
- void Cow.Walk() (which is the overriden method)
methods accesible with refrence Cow c = new Cow()
- void Cow.Walk() (which is the overriden method)
- void Cow.Milk()

(1. Actual Object)
As you can see both an and c has same type of methods.

(2. Object Refrence)
only the refrence that you use to access Cow() object limits the access to methods.
With c you can access void Cow.Milk() and void Cow.Walk()
but with an you can access void Cow.Walk() only.(which is the overriden method)

(1. Actual Object )
In this example above, when we create the object new Cow(), the methods it has are Cow.Milk() and virtual void Animal.Walk() but this Walk method is overriden by override void Cow.Walk() thus it has only to methods Cow.Milk() and Cow.Walk(). essentially when using override it replaces the virtual method.
(2. Object Refrence)
now based on what refrence you use for this object new Cow() that will determine what methods you can access. if you use Animal an reference then you can only use Cow.Walk() because the Animal refrence only has access to Animal.Walk Method which was replaced by Cow.Walk(). Thus an.Walk() will resolve to Cow.Walk(). where as Cow.Milk() exists on object but can not be called by Animal an refrence.

In general, the child reference has access to all the parent methods.

If you still didn't get the point you can experiment it yourself with inheritance and to examine the runtime behaviour you can use System.Refection ( I find it helpful to use in VS debugger Watch window as you can see in above Screengrab).

Some Basics about "new" modifier

new modifier creates the new method with same signature as inherited method. it has no connection no inheritance.
consider new methods as methods which only allow the class in which it was declared to have access.
Look at the following code similar to the above case.

    class Animal
    {
        public virtual void Walk() { }     //virtual here is optional
    }
    class Cow : Animal
    {
        public new void Walk() { }             // new here is also optional
        public void Milk() { }
    }

    static void Main()
    {
        Cow c = new Cow();

        // Note that I can also assign the Cow object to a Animal refrence
        Animal an = new Cow();

        c.Walk();       // calls Cow.Walk()
        an.Walk();      // calls Animal.Walk()
    }

Object
- new Cow()
- new Cow()
- both are same
methods in Object new Cow()
- void Cow.Milk()
- void Cow.Walk()
- void Animal.Walk()
methods accesible with refrence Animal an = new Cow()
- void Animal.Walk()
methods accesible with refrence Cow c = new Cow()
- void Cow.Walk() (which is the new method)
- void Cow.Milk()

(1. Actual Object)
similar to previous case both new Cow() objects contain same methods.
But in this case we have two Walk() methods in the object. (and one Milk() method)
One of them is Animal.Walk() and other is Cow.Walk() .
So when we used new instead of override it did not replace the base class method instead it created a new method with the same signature in the derived class.

Now that we know what all methods the object contain. we can determine the access rules by using refrence types.

(2. Object Reference)
The Object new Cow() contains two similar methods Animal.Walk() ,Cow.Walk().
when we call an.Walk() because the Animal an refrence has no access to any methods that its derived classes contains (general rule of inheritance). an.Walk() resolves to Animal.Walk().
When we call c.Walk() it resolves to Cow.Walk(). because the Cow c refrence has access to all methods of Animal and Cow (meaning access to all to three methods.). because we used new on Cow.Walk() it shadows the Animal.Walk() And thus call to c.Walk() resolves to Cow.Walk().

Example 1

using System;
using System.Reflection;

public class NewVsOverride
{
    public class Base
    {
        public virtual void Method1()
        {
            Console.WriteLine("Base - Method1");
        }

        public virtual void Method2()
        {
            Console.WriteLine("Base - Method2");
        }
    }

    public class Derived:Base
    {
        public override void Method1()
        {
            Console.WriteLine("Derived - Method1");
        }

        public new void Method2()
        {
            Console.WriteLine("Derived - Method2");
        }
    }

    public static void test()
    {
        Base bc = new Base();
        bc.Method1();  
        bc.Method2();

        Derived dc = new Derived();
        dc.Method1();
        dc.Method2();

        Base bcdc = new Derived();
        bcdc.Method1();
        bcdc.Method2();
    }
}

Object and Methods they contain. Base() | Derived() | Derived() ------------ | --- | --- Base.Method1() | (overriden)Derived.Method1()| (overriden)Derived.Method1() Base.Method2() | (Shadowed in Derived) Base.Method2()| (Shadowed in Derived) Base.Method2() -- | (new) Derived.Method2() | (new) Derived.Method2()
Refrences and Methods they can access bc | dc | bcdc ------------ | --- | --- bc.Method1() -> Base.Method1() | dc.Method1() -> (overriden)Derived.Method1()| bcdc.Method1() -> (overriden)Derived.Method1() bc.Method2() -> Base.Method2() | (Shadowed) Base.Method2() ( not accesible with Derived refrence)| bcdc.Method2() -> Base.Method2() (Shadowed in derived class not in base class.) -- | dc.Method2()-> (new) Derived.Method2() | (new) Derived.Method2() (Base ref has no access to child)

Example 2 (do it yourself)

Similarly try to understand the following example.
when calling test() from main.

using System;
using System.Reflection;
public class NewVsOverride2
{
    public class Base
    {
        public virtual void Method1()
        {
            Console.WriteLine("Base - Method1");
            Method2();  // will call Base.Method2 because Base.Method1 has no access to Shadowed new Derived.Method2
        }

        public virtual void Method2()
        {
            Console.WriteLine("Base - Method2");
        }
    }

    public class Derived : Base
    {
        //comment Derived.Method1 for test2
        public override void Method1()
        {
            Console.WriteLine("Derived - Method1");
            Method2(); //will call Derived.Method2 because In Derived Method2 is shadowed 
        }

        public new void Method2()
        {
            Console.WriteLine("Derived - Method2");
        }
    }

    public class Derived2 : Derived
    {
        public override void Method1()
        {
            Console.WriteLine("Derived2 - Method1");
        }

        public new void Method2()
        {
            Console.WriteLine("Derived2 - Method2");
        }
    }

    public static void test()
    {
        test0();

        Console.WriteLine();
        test1();
        Console.WriteLine();

        test2();

    }

    public static void test0()
    {
        Base bc = new Base();
        bc.Method1();
        bc.Method2();

        Derived dc = new Derived();
        dc.Method1();
        dc.Method2();

        Base bcdc = new Derived();
        bcdc.Method1();
        bcdc.Method2();

        Derived2 d2 = new Derived2();
        d2.Method1();
        d2.Method2();
    }

    public static void test1()
    {
        Derived dc = new Derived();
        dc.Method1();
        Base bcdc = dc;
        bcdc.Method1();
        dc.Method2();
    }

    //comment Derived.Method1 for test2
    public static void test2()
    {
        Derived dc = new Derived();
        dc.Method1();
        Base bcdc = dc;
        bcdc.Method1();
        dc.Method2();
    }
}

Note: for test2 comment Derived.Method1
Output:

//test0
Base - Method1
Base - Method2
Base - Method2
Derived - Method1
Derived - Method2
Derived - Method2
Derived - Method1
Derived - Method2
Base - Method2
Derived2 - Method1
Derived2 - Method2

//test1
Derived - Method1
Derived - Method2
Derived - Method1
Derived - Method2
Derived - Method2

//test2
Base - Method1
Base - Method2
Base - Method1
Base - Method2
Derived - Method2

if you understood outputs for test1() and test2() . I think that will be it.

Refrences:
https://stackoverflow.com/a/11046733/15225066
https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/classes-and-structs/knowing-when-to-use-override-and-new-keywords
https://stackoverflow.com/questions/17717570/why-does-calling-a-method-in-my-derived-class-call-the-base-class-method
https://stackoverflow.com/questions/11046387/exact-difference-between-overriding-and-hiding

Generate all kinds of permutations and combinations using backtracking/recursion

dhavalraj007 — Thu, 19 Aug 2021 10:12:57 +0000

There are four kinds of permutations or combinations possible based on whether repetition is allowed or not and whether order matters or not.
All four of them are summarized and explained by example in the below figure.

To generate them using recursion we make the recursion tree.

All the combinations in this tree are the first type of permutations(n^r). if the repetitions are not allowed but the order matters then you just skip the blue ones. the point to not here is that we skipped those items here which are same as the parent node like for 2's children we skipped when 2 2 came, for 3's children we skipped when 3 3 came. So this will take care of the repetitions thing. now if the order does not matter then we cant take both 1 2 and 2 1.In the figure we skip green ones. Notice here that we only skip the children elements who are less then the parent or you can say we take elements starting from the parent itself. for example, for 1's children we start taking elements from 1 , like 1 1 ,1 2 ,1 3 for 2's children we start taking elements from 2 , like 2 2, 2 3 and for 3's children we start taking elements from 3,like 3 3.
Based on following observations here is the Cpp code

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

void permComb(vector<int> data, int r, bool order, bool repeat, vector<int> out = {}, int i = 0, unordered_set<int> set = {})
{
    if (out.size() == r)
    {
        print(out);
        return;
    }

    for (int next = (order ? 0: i); next < data.size(); next++)
    {
        if (!repeat and set.find(data[next])!=set.end()) continue;
        set.insert(data[next]);     // to track repetitions
        out.push_back(data[next]);
        permComb(data, r, order, repeat, out, next, set);
        out.pop_back();
        set.erase(data[next]);
    }
    return;
}


int main()
{
    vector<int> data{ 1,2,3 };
    permComb(data, 3, true, false);
    return 0;
}

Update:

I just realized using array to handle repetitions is more faster.
If you want only the fourth type of combination (which is all subset) this code can be optimized by removing the unordered set and at each choice passing next+1 as parameter instead of next.(the reason can be found in the recursion tree for the fourth type).or It can also be solved by considering a different recursive tree approach which goes like should I consider the first element in or not and so on for all. this can also be solved by bit-masking.
I started Learning Dynamic programming, And the first problem I encountered was 0-1 knapsack problem.in this problem we are given a bunch of items with values and associated weight and also given a knapsack of capacity W to put items into. And we need to find the maximum profit achieved by choosing items and putting it into knapsack. If you think about it this problem demands no order and no repetition which is type 4 (or subset) type problem. so this can be solved by backtracking also.
If any problem you find is demanding any different type of permutations then first try to draw the recursive tree like the first type and then try to cross out the options which does not fit in your solutions and then try to augment that into the code snippet. For example, I was doing a letter tile possibilities problem on leetcode. which demanded that the certain characters can be used only fixed amount of times in a sequence. I solved it using the idea I got from the cross check method I described.

let me know your thoughts in the comments.👋

Understanding Backtracking/Recursion

dhavalraj007 — Sun, 15 Aug 2021 09:59:15 +0000

Abstract Pseudo code to help understand the gist of backtracking

bool Solve(configuration conf)
{
    if (no more choices) // BASE CASE
       return (if conf is goal state);

    for (all available choices)
    {
        try one choice c;
        // recursively solve after making choice
        ok = Solve(updated conf with choice c made);
        if (ok)
           return true;
        else
           unmake choice c;
    }

return false; // tried all choices, no soln found
}

When you need to find all possible solutions

void Solve(configuration conf,solutions& sols)
{
    if (no more choices) // BASE CASE
       if conf is goal state
           sols.add(conf);
       return;

    for (all available choices)
    {
        try one choice c;
        // recursively solve after making choice
        Solve(updated conf with choice c made);
        unmake choice c;
    }

return; // tried all choices, no soln found
}

Examples:

N-Queens

Problem statement

Given a grid of size NxN arrange N queens in a grid such that no queen attacks other.

Input:

N = 4

Output:

Pseudo Code

bool solve(grid,queens)
{
    //if(no more choices) //conf is goal state // BASE CASE
    if(queens==0)           
        return true;

    //for (all available choices)
    for(all safe grid cell c)
    {
        //try one choice c;
        // recursively solve after making choice
        put queen at cell c;
        // ok = Solve(updated conf with choice c made);
        ok = solve(grid,queens-1);

        if(ok)
            return true;
        else
            remove queen from cell c;   //unmake choice c;
    }

    return false;       // tried all choices, no soln found
}

Cpp code

//checks whether the cell (i,j) is unsafe or safe
bool is_Atttacked(int i, int j, vector<vector<int>>& grid)
{
    int N = grid.size();
    for (int ele : grid[i])
    {
        if (ele == 1)
            return true;
    }


    for (int row = 0; row < N; row++)
    {
        if (grid[row][j] == 1)
            return true;
    }

    for (int y = 0; y < N; y++)
    {
        int x = (i - j) + y;
        if (x >= 0 and x < N)
        {
            if (grid[x][y] == 1)
                return true;
        }
    }


    for (int y = 0; y < N; y++)
    {
        int x = (i + j) - y;
        if (x >= 0 and x < N)
        {
            if (grid[x][y] == 1)
                return true;
        }
    }

    return false;
}

//main recursive function
bool NQueens(vector<vector<int>>& grid, int N)
{
    if (N == 0)
        return true;

    for (int i = 0; i < grid.size(); i++)
    {
        for (int j = 0; j < grid.size(); j++)
        {
            if (is_Atttacked(i, j, grid))
                continue;

            grid[i][j] = 1;

            if (NQueens(grid, N - 1))
                               return true;
                        else
                    grid[i][j] = 0;
        }
    }
    return false;
}

Knights Tour

Problem statement

Given a NxN board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each the cell in which they are visited.

Input:

N = 5

Output:

0  5  14 9  20 
13 8  19 4  15 
18 1  6  21 10 
7  12 23 16 3 
24 17 2  11 22

Pseudo code

//grid filled with -1 and grid[0][0] = 0 , steps = 1 , x=y=0
bool solve(grid,steps,x,y)
{
    if(steps==grid.size()^2)
    {
        print(grid);
        return true;
    }

    for(all possible/safe moves from (x,y))
    {
        grid[move.x][move.y] = steps;
        ok = solve(grid,steps+1,move.x,move.y);
        if(ok)
            return true;
        else
            grid[move.x][move.y] = -1;
    }
    return false;
}

Cpp code

#include <iostream>
#include <vector>

using namespace std;


void print(vector<vector<int>> &grid)
{
    for(auto row:grid)
    {
        for(auto ele:row)
        {
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


int isSafe(int x, int y,vector<vector<int>>& grid )
{
    return (x >= 0 && x < grid.size() && y >= 0 && y < grid.size()
            && grid[x][y] == -1);
}

bool solve(vector<vector<int>> grid,int steps,int x,int y,vector<int> &xMove,vector<int> &yMove)
{

    if(steps == grid.size()*grid.size())
    {
        print(grid);
        return true;
    }
    for(int i=0;i<8;i++)    //for all possible moves from (x,y)
    {
        int Xnext = x+xMove[i];
        int Ynext = y+yMove[i];
        if(isSafe(Xnext,Ynext,grid))
        {
            grid[Xnext][Ynext]=steps;
            int ok = solve(grid,steps+1,Xnext,Ynext,xMove,yMove);
            if(ok)
                return true;
            else
                grid[Xnext][Ynext] = -1;
        }
    }

    return false;
}


int main() {
    int N = 5;
    vector<vector<int>> grid(N,vector<int>(N,-1));
    grid[0][0] = 0;
    vector<int> xMove{ 2, 1, -1, -2, -2, -1, 1, 2 };
    vector<int> yMove{ 1, 2, 2, 1, -1, -2, -2, -1 };

    solve(grid,1,0,0,xMove,yMove);
}

Cpp code for all possible solutions

#include <iostream>
#include <vector>

using namespace std;

void print(vector<vector<int>> &grid)
{
    for(auto row:grid)
    {
        for(auto ele:row)
        {
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


int isSafe(int x, int y,vector<vector<int>>& grid )
{
    return (x >= 0 && x < grid.size() && y >= 0 && y < grid.size()
            && grid[x][y] == -1);
}


void solve(vector<vector<int>> grid,int steps,int x,int y,vector<int> &xMove,vector<int> &yMove)
{

    if(steps == grid.size()*grid.size())
    {
        print(grid);
        return;
    }
    for(int i=0;i<8;i++)    //for all possible moves from (x,y)
    {
        int Xnext = x+xMove[i];
        int Ynext = y+yMove[i];
        if(isSafe(Xnext,Ynext,grid))
        {
            grid[Xnext][Ynext]=steps;
            solve(grid,steps+1,Xnext,Ynext,xMove,yMove);
            grid[Xnext][Ynext] = -1;
        }
    }

    return;
}


int main() {
    int N = 5;
    vector<vector<int>> grid(N,vector<int>(N,-1));
    grid[0][0] = 0;
    vector<int> xMove{ 2, 1, -1, -2, -2, -1, 1, 2 };
    vector<int> yMove{ 1, 2, 2, 1, -1, -2, -2, -1 };

    solve(grid,1,0,0,xMove,yMove);
}

Find all Paths in a Maze/Rat in a Maze

Problem Statement:

Given a binary matrix of size NxN find and print Path from top left corner to bottom right corner.

Input:

Output:

Cpp code for all Possible Paths

#include <iostream>
#include <vector>

using namespace std;

void print(vector<vector<int>>& grid)
{
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<grid.size();j++)
        {
            cout<<grid[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}


bool isValid(vector<vector<int>> &maze,vector<vector<int>> &ans,int x,int y)
{
    return (x>=0 and x<maze.size() and y>=0 and y<maze.size() and maze[x][y]==1 and ans[x][y]==0);
}

void findPath(vector<vector<int>> &maze,vector<vector<int>> ans,int x,int y)
{
    if(ans[maze.size()-1][maze.size()-1] == 1)
        {
            print(ans);
            return;
        }

    if(isValid(maze,ans,x+1,y))     //down
    {
        ans[x+1][y] = 1;
        findPath(maze,ans,x+1,y);
        ans[x+1][y] = 0;
    }

    if(isValid(maze,ans,x-1,y))     //up
    {
        ans[x-1][y] = 1;
        findPath(maze,ans,x-1,y);
        ans[x-1][y] = 0;
    }

    if(isValid(maze,ans,x,y+1))     //right
    {
        ans[x][y+1] = 1;
        findPath(maze,ans,x,y+1);
        ans[x][y+1] = 0;
    }

    if(isValid(maze,ans,x,y-1))     //left
    {
        ans[x][y-1] = 1;
        findPath(maze,ans,x,y-1);
        ans[x][y-1] = 0;
    }
    return;
}

int main() {
    int x,y;
    x=0,y=0;

    vector<vector<int>> maze = { 
                    { 1, 0, 0, 0 },
                    { 1, 1, 1, 1 },
                    { 0, 1, 0, 1 },
                    { 1, 1, 1, 1 } };
    int N = maze.size();
    vector<vector<int>> ans(N,vector<int>(N,0));
    ans[0][0] = 1;

    findPath(maze,ans,x,y);
}

Find all possible combinations satisfying given constraints

Problem Statement

Given a number N find all possible combination of 2N numbers such that every element from 1 to 2N appears exactly twice and the distance between them is equal to that number.

Input:

N = 3

Output:

 3 1 2 1 3 2
 2 3 1 2 1 3

In this problem, recursive tree can be formed in two ways. first way is you first consider N elements as choices and other is you consider 2N positions as choices. In first way you choose one of N elements and place it at the 0th position in array and then you recurs for all other indices(here you need to have some way to not put the number more than once). In second way you take first element from N and choose one of 2N locations to put the first element and recurs for all other N-1 numbers. as the second way seems much easy we will implement that.

Pseudo Code

void solve(array,n)
{
    if(n becomes 0)
    {
        print array
        return;
    }

    for(all indices i in array)
    {
        if(inserting in n in array at index i is safe)  // safe means array[i] and array[i+n+1] is free
        {
            array[i] = n;       // put n at i and i+n+1
            array[i+n+1] = n;

            solve(array,n-1);   //recur for all n-1 numbers

            array[i] = -1;      //unmake choice
            array[i+n+1] = -1;
        }
    }
    return; //no soln found
}

Cpp code

#include <iostream>
#include <vector>

using namespace std;

void print(vector<int> ar)
{
    for(auto e:ar)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

bool is_safe(vector<int> array,int n,int i)
{
    return (i<array.size() and i+n+1<array.size() and array[i]==-1 and array[i+n+1]==-1);
}


void solve(vector<int> array,int n)
{
    if(n==0)
    {
        print(array);
        return;
    }

    for(int i=0;i<array.size();i++)
    {
        if(is_safe(array,n,i))
        {
            array[i] = n;
            array[i+n+1]=n;
            solve(array,n-1);
            array[i] = -1;
            array[i+n+1] = -1;
        }
    }
    return;
}

int main() {
    int N = 7;
    vector<int> v(2*N,-1);
    solve(v,N);
}

K - Partitions

Problem Statement

Given an array of integers Partition the array into K subsets having equal sum.

Input:

k = 3
array = 7 3 5 12 2 1 5 3 8 4 6 4

Output:

7 3 5 2 3 
12 8 
1 5 4 6 4

In this problem, for each element we have to choose one of k partitions. So choices are k partitions and then we recurs for all other elements.
Pseudo code

bool solve(partitons,sums,array,index,k)
{
    if(index is at end of array +1 and all the sums are equal)
    {
        print partitions;
        return true;
    }
    else if(index is at the ened of array +1 and all sums are not equal)
        return false;

    //choices for arrray[index] element
    for(all the part in partitions)
    {
        part.add(array[index])
        correspnding sum in sums+= array[index]
        //recurs for next element
        ok = solve(partitions,sums,array,index+1,k);    
        if(ok)
            return true;
        else
        {
            part.pop()
            correspnding sum in sums-= array[index];
        }
    }
    return false;   //all choices tried no solutions.
}

Cpp code

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void print(vector<vector<int>> grid)
{
    for(auto row:grid)
    {
        for(auto ele:row)
        {
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

void print(vector<int> v)
{
    for(auto ele:v)
        cout<<ele<<" ";
        cout<<endl;
}

bool solve(vector<vector<int>> parts,vector<int> sums,vector<int> vec,int index,int k)
{
   // if reached the end and all partition sum is equal
    if(index == vec.size() and all_of(begin(sums),end(sums),[&sums](int val){return val==sums[0];}))
    {
        print(parts);
        return true;
    }
    // if reached the end but all partition sum is not equal
    else if(index>=vec.size())
    {
        return false;
    }

    for(int i=0;i<k;i++)
    {
        parts[i].push_back(vec[index]);
        sums[i] += vec[index];
       // print(sums);
        bool ok = solve(parts,sums,vec,index+1,k);
        if(ok)
        {
            return true;
        }
        else
        {
            parts[i].pop_back();
            sums[i] -= vec[index]; 
        }
    }

    return false;
}

int main() {
    vector<int> vec{7, 3, 5, 12, 2, 1, 5, 3, 8, 4, 6, 4};
    int k = 3;
    vector<int> sums(k,0);
    vector<vector<int>> parts(k,vector<int>());
    solve(parts,sums,vec,0,k);
}

Print All Combinations with repetitions allowed

Problem Statement

Given a array and an integer k print its all k element combinations with repetitions allowed.
update: I got a more general idea about this problem and made a separate post about it. check out it here.

Input:

k = 2
array = { 1, 2, 3 }

Output

1 1  1 2  1 3  2 2  2 3  3 3

Input:

k = 3
array = { 1, 2, 3, 4 }

Output

1 1 1  1 1 2  1 1 3  1 1 4  1 2 2  1 2 3  1 2 4  1 3 3   1 3 4  1 4 4  2 2 2  2 2 3  2 2 4  2 3 3  2 3 4  2 4 4   3 3 3  3 3 4  3 4 4  4 4 4

First of all Notice that this is the standard permutations and combination thing. See the figure below.

As our problem requires no order and repetitions the formula is the third one( if you wanna know how check out this page). And that formula gives the number answers for our problem. But that doesn't help.
Notice the the pattern in the first column of the third table. To solve this problem using recursion, we first think of what choices are we making. hmmm, we are making an smaller array of k-elements from the bigger input data array. and for each of the index of smaller array we are making choices as to what to put at that index. for the index 0 of k-element array we can have all the elements from the bigger array. at the next index (referring to children calls) we can have only elements after that element(referring to current parent node). its little confusing. to make it easier to understand look at the recursion tree for the first input provided above.

here if you observe the node 2_ then at the next level you can only have elements after and including 2. (this is just to avoid the reverse copies that is because 12 and 21 are same thing).

Cpp Code

#include <iostream>
#include <vector>

using namespace std;

void print(vector<int> data)
{
    for (auto e : data)
    {
        cout << e << " ";
    }
    cout << endl;
}

//data index is the index for the actual data and out_index is for output k-element array
void solve(vector<int> data, int data_index, vector<int> out, int out_index)
{
    if (out_index == out.size())
    {
        print(out);
        return;
    }

    for (int i = data_index; i < data.size(); i++)
    {
        if(out[out_index]==-1)
            out[out_index] = data[i];
        solve(data,i, out, out_index + 1);
        out[out_index] = -1;
    }

    return;
}

int main() {
    vector<int> data{ 1,2,3,4 };
    int r = 3;
    vector<int> out(r, -1);
    solve(data, 0, out, 0);
}

Print all combinations of numbers from 1 to n having sum n

Problem statement

Print all combinations of numbers from 1 to n having sum n

Input:

n = 3

Output:

1 1 1
1 2
3

Input:

n = 4

Output:

If you observe this problem carefully and you have read my permutation and combination post then you might identify solution to this problem.
In this problem it is clear that repetitions are allowed and order does not matter. and the set to choose the elements from is 1...sum . so n is sum but we don't know r which is the length of the combination. (remember in the recursive tree shown in the PNC (permutation and combination) post has intermediate nodes , these nodes are also partial combinations for example if you take all the nodes for the tree of the fourth type of combination then you will find something called powerset (set of all subsets)). We decrement the sum as we go deep and at each node we check if sum==0 and if it is then that partial solution is our one of possible solution. to take care of the order thing, In the for loop we start from the parent node.( Again if you don't know what I am talking about please checkout my PNC post.)
Cpp code

#include <iostream>
#include <vector>


using namespace std;

void print(vector<int> data)
{
    for (auto e : data)
    {
        cout << e << " ";
    }
    cout << endl;
}


void solve(int i,int n,int sum,vector<int> out)
{

    if (sum == 0)
    {
        print(out);
        return;
    }
    if (sum < 0)
    {
        return;
    }

    for (int x = i; x <= n; x++)
    {
        out.push_back(x);
        sum -= x;
        solve(x, n, sum, out); 
        sum += x;
        out.pop_back();
    }
    return;
}


int main() {
    int sum = 4;
    solve(1, sum, sum, vector<int>());
}

Print all triplets in an array with a sum less than or equal to a given target

Problem Statement

Print all triplets in an array v with a sum less than or equal to a given target

Input:

target = 10
v = { 2, 7, 4, 9, 5, 1, 3 }

Output:

In this problem r is fixed at 3. And n is the size of the array. And the set to choose values from is array v. In this problem the order does not matter and repetitions are also not allowed. So this is the fourth type of combination.
Cpp code

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void print(vector<int> data)
{
    for (auto e : data)
    {
        cout << e << " ";
    }
    cout << endl;
}

void solve(vector<int> v, int target, int r, int sum, vector<int> out = {}, int i = -1)
{
    if (r == 0 and sum <= target)
    {
        print(out);
        return;
    }
    if (sum > target)
    {
        return;
    }

    for (int x = (i==-1?0:i); x < v.size(); x++)
    {
        if (x == i) continue;
        out.push_back(v[x]);
        sum += v[x];
        r--;
        solve(v,target,r,sum,out,x);
        r++;
        sum -= v[x];
        out.pop_back();
    }
    return;
}


int main()
{
    vector<int> v{ 2, 7, 4, 9, 5, 1, 3 };
    int target = 10;
    solve(v, target,3,0);
    return 0;
}

Find all combinations of non-overlapping substrings of a string

Problem statement

Find all combinations of non-overlapping parenthesized substrings of a string

Input:

"ABC"

Output:

(ABC)
(AB) (C)
(A) (BC)
(A) (B) (C)

To solve this question, Notice where you put spaces, design the recursive tree. and then implement it.

Cpp code

void solve(string data,int index,int n)
{
    if (n == 1)
    {
        cout <<"(" << data <<")" << endl;
        return;
    }
    n--;
    solve(data, index + 1, n);
    data.insert(index, ") (");
    solve(data, index + 4, n);  // +4 because insert added 3 extra chars
    //no need to remove em because this is the last choice
}

int main()
{
    string s = "ABC";
    solve(s,1,s.length());
    return 0;
}

// to be continued