Q:

An algorithm to generate subsets of a set satisfying certian conditions

Suppose I am given a sorted list of elements and I want to generate all subsets satisfying some condition, so that if a given set does not satisfy the condition, then a larger subset will also not satisfy it, and all sets of one element do satisfy it. 
For example, given a list of all positive integers smaller than 100, determine subsets whose sum is smaller than 130: (100,29) (0,1,40), (0), etc...
How can I do that (preferably in Python)? 
Thanks! :) 

A:

You can generate all the subsets using a Branch-and-bound technique: you can generate all the subsets in an incremental fashion (generating superset of subsets already determined), using as a prune condition "does not explore this branch of the tree if the root does not satify the constraint". 
If you want to be generic regarding the constraint, I think this is the best strategy. 
Be sure to write in a correct manner the code that generates the subsets, otherwise you generate many time the same subsets: in order to avoid memoization, which can be time-consuming due to map lookups and introduce memory overhead, you can generate the subsets in that manner:
GetAllSubsets(List objects) {
    List generated = {};
    GetAllSubsets(generated, [], objects);
    return generated;
}

GetAllSubsets(List subsetGenerated, List objectFixed, List objectsToFix) {
    GetAllSubsets(subsetGenerated, objectFixed, objectsToFix.sublist(1, objectsToFix.length());
    if (satisfy(toCheck = objectsFixed.add(objectsToFix.get(0)))) {
        subsetGenerated.add(toCheck);
        GetAllSubsets(subsetGenerated, toCheck, objectsToFix.sublist(1, objectsToFix.length());
    }
}

In fact, the subsets added by the first invocation of GetAllSubsets doesn't have the first element of objectsToFix, where the subsets added by the second call (if the pruning condition isn't violated) have that element, so the intersection of the two sets of subsets generated is empty.