Subset equilibrium

You are given an array of numbers.

Write a script to find all proper subsets with more than one element where the sum of the elements equals the sum of their indices.

Clarification from Peter: ... equals the sum of their 1-based indices in the original array.

Examples

Example 1
Input: @nums = (2, 1, 4, 3)
Output: (2, 1), (1, 4), (4, 3), (2, 3)
Subset 1: (2, 1)
Values: 2 + 1 = 3
Positions: 1 + 2 = 3
Subset 2: (1, 4)
Values: 1 + 4 = 5
Positions: 2 + 3 = 5
Subset 3: (4, 3)
Values: 4 + 3 = 7
Positions: 3 + 4 = 7
Subset 4: (2, 3)
Values: 2 + 3 = 5
Positions: 1 + 4 = 5

Example 2
Input: @nums = (3, 0, 3, 0)
Output: (3, 0), (3, 0, 3)
Subset 1: (3, 0)
Values: 3 + 0 = 3
Positions: 1 + 2 = 3
Subset 2: (3, 0, 3)
Values: 3 + 0 + 3 = 6
Positions: 1 + 2 + 3 = 6

Example 3
Input: @nums = (5, 1, 1, 1)
Output: (5, 1, 1)
Subset 1: (5, 1, 1)
Values: 5 + 1 + 1 = 7
Positions: 1 + 2 + 4 = 7

Example 4
Input: @nums = (3, -1, 4, 2)
Output: (3, 2), (3, -1, 4)
Subset 1: (3, 2)
Values: 3 + 2 = 5
Positions: 1 + 4 = 5
Subset 2: (3, -1, 4)
Values: 3 + (-1) + 4 = 6
Positions: 1 + 2 + 3 = 6

Example 5
Input: @nums = (10, 20, 30, 40)
Output: ()

Analysis

This is an interesting challenge in that when forming the subsets we need to keep track of the location of each entry in the original array. This is particularly important when there are duplicate values in that array - see example 2.

So rather than subsetting the original array I subsetted the array 1, 2, 3 ... up to the number of elements in the supplied array. Note that these numbers are 1 more than the corresponding perl 0-based indices.

It's not hard to do the subsetting in Perl, but as usual I resorted to the Algorithm::Combinatorics module, which is fast and easy to use.

I then dereference each subset to the @input and @indices arrays to get the set of values and positions (ie indices + 1) of each subset component, compute the total of each of these and discard the subset unless those are equal.

The rest is just formatting to generate something equivalent to the examples.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-04-27
use utf8;     # Week 371 - task 2 - Subset equilibrium
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;
use Algorithm::Combinatorics ('subsets');

subset_equilibrium(2, 1, 4, 3); 
subset_equilibrium(3, 0, 3, 0);
subset_equilibrium(5, 1, 1, 1);
subset_equilibrium(3, -1, 4, 2);
subset_equilibrium(10, 20, 30, 40);
subset_equilibrium(0, 3, 11, 2, -2, 4);

sub subset_equilibrium {
    
    my (@input, %in_index, $iter, $no, $ss, $sum_val, $sum_pos, @values, @positions, $j, $k, $output,
        $subsets, $details, @indices);
    
    # initialise
    @input = @_;
    
    # put 1-based positions into array and get subsets
    push @indices, $_ + 1 for 0 .. @input - 1;
    $iter = subsets(\@indices);
    
    # iterate over subsets
    $no = 1;
    $subsets = $details = '';
    while ($ss = $iter->next) { 
        next if @$ss <= 1 or @$ss == @indices;
        
        # add up values and positions for this subset
        $sum_val = $sum_pos = 0;
        @values = @positions = ();
        for $j (0 .. @$ss - 1) {
            $k = $ss->[$j] - 1;
            push @values, $input[$k];
            push @positions, $indices[$k];
            $sum_val += $input[$k];
            $sum_pos += $indices[$k];
        }
        
        # discard unless sum of values = sum of positions
        next unless $sum_val == $sum_pos;
        $subsets .= '(' . join(', ', @values) . '), ';
        $details .= 
            qq[\n   subset $no: (] . join(', ', @values) . ')' .
            qq[\n      values: ] . join(' + ', @values) . ' = ' . $sum_val . 
            qq[\n      positions: ] . join(' + ', @positions) . ' = ' . $sum_pos;  
        $no ++;
    }
    
    # report
    say qq[\nInput:  (] . join(', ', @input) . ')';
    print qq[Output: ] . ($subsets ? substr($subsets, 0, -2) . qq[$details\n] : qq[none\n]);
}

33 lines of code

Output

Input:  (2, 1, 4, 3)
Output: (4, 3), (2, 3), (1, 4), (2, 1)
   subset 1: (4, 3)
      values: 4 + 3 = 7
      positions: 3 + 4 = 7
   subset 2: (2, 3)
      values: 2 + 3 = 5
      positions: 1 + 4 = 5
   subset 3: (1, 4)
      values: 1 + 4 = 5
      positions: 2 + 3 = 5
   subset 4: (2, 1)
      values: 2 + 1 = 3
      positions: 1 + 2 = 3

Input:  (3, 0, 3, 0)
Output: (3, 0, 3), (3, 0)
   subset 1: (3, 0, 3)
      values: 3 + 0 + 3 = 6
      positions: 1 + 2 + 3 = 6
   subset 2: (3, 0)
      values: 3 + 0 = 3
      positions: 1 + 2 = 3

Input:  (5, 1, 1, 1)
Output: (5, 1, 1)
   subset 1: (5, 1, 1)
      values: 5 + 1 + 1 = 7
      positions: 1 + 2 + 4 = 7

Input:  (3, -1, 4, 2)
Output: (3, 2), (3, -1, 4)
   subset 1: (3, 2)
      values: 3 + 2 = 5
      positions: 1 + 4 = 5
   subset 2: (3, -1, 4)
      values: 3 + -1 + 4 = 6
      positions: 1 + 2 + 3 = 6

Input:  (10, 20, 30, 40)
Output: none

Input:  (0, 3, 11, 2, -2, 4)
Output: (3, 11, -2, 4), (3, 11, 2, -2), (0, 11, -2), (0, 3)
   subset 1: (3, 11, -2, 4)
      values: 3 + 11 + -2 + 4 = 16
      positions: 2 + 3 + 5 + 6 = 16
   subset 2: (3, 11, 2, -2)
      values: 3 + 11 + 2 + -2 = 14
      positions: 2 + 3 + 4 + 5 = 14
   subset 3: (0, 11, -2)
      values: 0 + 11 + -2 = 9
      positions: 1 + 3 + 5 = 9
   subset 4: (0, 3)
      values: 0 + 3 = 3
      positions: 1 + 2 = 3