1

A common pattern I like to use in python is to have a recursive function within a function. For example a short recursive way to find all possible subset sums of an array:

def all_sums(arr):

    res = set()
    def dfs(index, current_sum):
        if index == len(arr): 
            res.add(current_sum)
            return
        dfs(index + 1, current_sum + arr[index])
        dfs(index + 1, current_sum)
    dfs(0, 0)
    return res

This is very nice and simple so I was wondering if there is a way to reproduce this in C++. I've saw this question, so I tried something like so:

# include<bits/stdc++.h>
using namespace std;

unordered_set<int> all_sums(vector<int> &arr){
    unordered_set<int> res;
    auto dfs = [&](int index, int current_sum){
        if(index == arr.size()){
            res.insert(current_sum);
            return;
        }
        dfs(index + 1, current_sum + arr[index]);
        dfs(index + 1, current_sum);
    };
    dfs(0, 0);
    return res;
}

This fails because dfs can't appear in it's own initializer. I'm wondering if there is a nice way to have the "recursive function within function" functionality in C++.

Primusa
  • 13,136
  • 3
  • 33
  • 53

0 Answers0