Python - Unexpected behavior when generating the powerset in range [0, n-1]

Question

I am trying to recursively generate the powerset in the range [0, n - 1] without passing extra parameters to the inner search function.

def powerSet(n):
  all_subsets = []
  curr_subset = []
  
  def search(c):
    if c == n:
      all_subsets.append(curr_subset)
    else:
      search(c + 1)
      curr_subset.append(c)
      search(c + 1)
      curr_subset.pop()

  search(0)
  
  return all_subsets

Upon running the following statement:

print(powerSet(3))

I was expecting it to return some ordering of:

[[0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]

Instead, I was astonished to get the following output:

[[], [], [], [], [], [], [], []]

Intrigued, I moved the inner-function outside and used a parameterised approach, only to still get the same output:

def search(c, curr_subset, all_subsets, n):
  if c == n:
    all_subsets.append(curr_subset)
  else:
    search(c + 1, curr_subset, all_subsets, n)
    curr_subset.append(c)
    search(c + 1, curr_subset, all_subsets, n)
    curr_subset.pop()

def powerset2(n):
  all_subsets = []
  curr_subset = []
  search(0, curr_subset, all_subsets, n)
  
  return all_subsets

print(powerset2(3)) # [[], [], [], [], [], [], [], []]

I like to think I know a little bit about Python, but this behavior has me very perplexed. I coded the same recursive algorithm in C++ with global variables, and got the desired powerset, which I verified through a simple printing function:

int n = 3;
vector<vector<int>> powerset;
vector<int> subset;


void search(int k) {
  if (k == n) {
    powerset.push_back(subset);
  } else {
    search(k+1);
    subset.push_back(k);
    search(k+1);
    subset.pop_back();
  }
}

void printer(){
  cout << "{ ";
  for (auto ele: powerset) {
    cout << "{";
    for (auto ele2: ele)
      cout << ele2 << ", ";
    cout << "}, ";
  }
  cout << "}" << "\n";
}

int main() {
  search(0);
  printer(); /* { {}, {0, }, {0, 1, }, {0, 1, 2, }, {0, 2, }, {1, }, {1, 2, }, {2, }, } */
  return 0;
}

Is there any way to retain the nested-function Python approach from the beginning and still generate the powerset?

Answer 1

Change

all_subsets.append(curr_subset)

in the original to

all_subsets.append(curr_subset[:])

You need to capture the contents of curr_subset at the time it's being appended. As is, you merely append 8 instances of the same list, which is empty by the time your function ends.