Maximum summed sub sequences with no two numbers sharing the same digit [closed]

Suppose there are 5 positive integers in an array or list as 14, 12, 23, 45, 39.

14 and 12 cannot be taken in the subset as 1 is common in both. Similarly {12, 23}, {23, 39}, {14, 45} cannot be included in the same subset.

So the subset which forms the maximum sum is {12, 45, 39}. The maximum sum such formed is 96.

the result should be the maximum sum of such combination.

Sample TestCase 1 Input 3,5,7,2 Output 17

Sample Test Case 2 Input 121,23,3,333,4 Output 458

Sample Test Case 3 Input 32,42,52,62,72,82,92 Output 92

Explanation

Test Case 1: {3, 5, 7, 2} = 17

Test Case 2: {121, 333, 4} = 458

Test Case 3: {92} = 92

• thanks for the information, i've tagged it appropriately. – biziden May 24 '19 at 13:13
• Welcome to PPCG! – AdmBorkBork May 24 '19 at 13:59
• Is this challenge from another programming contest site? – xnor May 24 '19 at 15:40
• Why did you remove the winning criterion? Doing so makes the challenge off-topic. – Arnauld May 24 '19 at 16:45
• ...plus there are already nine answers using code-golf as a winning criteria. – Jonathan Allan May 24 '19 at 18:04

05AB1E, 11 bytes

æʒ€ÙJDÙQ}OZ


Try it online!

Explanation

æʒ      }    # filter the powerset of the input, keep only elements
€Ù         # where each number with duplicate digits removed
JDÙQ     # have different digits from the other numbers
O   # sum each
Z  # take max

• Test Case 2: {121, 333, 4} = 458 – Jonathan Allan May 24 '19 at 14:27
• @JonathanAllan: Ah OK. Same digits in a number is okay. Fixed :) – Emigna May 24 '19 at 14:43

Wolfram Language (Mathematica), 77 bytes

Max[Tr/@Select[(s=Subsets)@#,!Or@@IntersectingQ@@@s[IntegerDigits/@#,{2}]&]]&


Try it online!

• thanks for the solution, could you please explain, as I have limited knowledge of Wolfram Langauge. – biziden May 24 '19 at 14:29

Python 2, 137112105119 116 bytes

lambda a,s='':a and max([x+f(a[1:],y)for x,y in(0,s),(a[0],s+set(a[0]))if max(map(y.count,'1234567890'))<2])or 0


Try it online!

Python 3.8 (pre-release), 116 bytes

lambda a,s='':a and max(x+f(a[1:],y)for x in(0,a[0])if max(map((y:=s+str(set(str(x)*x))).count,'1234567890'))<2)or 0


Try it online!

• Thanks for the solution, added more test cases. – biziden May 24 '19 at 13:33
• Failing the second test case. Sample Test Case 2 Input 121,23,3,333,4 Output 458 – biziden May 24 '19 at 13:51
• Needs more work I think since print f([121,23,3,333,4]) in the TIO returns 27, not 458. – Kjetil S. May 24 '19 at 14:03
• @biziden Fixed. – TFeld May 24 '19 at 15:28
• @KjetilS. Fixed – TFeld May 24 '19 at 15:28

JavaScript (ES6), 77 bytes

f=([n,...a],s=m=0,p='')=>n?f(a,s,p,p.match([${n}])||f(a,s+n,p+n)):m=m>s?m:s  Try it online! Commented f = ( // f is a recursive function taking: [n, ...a], // n = next value from a[]; a[] = remaining values s = // s = current sum m = 0, // m = maximum sum, which is eventually returned p = '' // p = all previous digits, as a string ) => // n ? // if n is defined: f( // do a recursive call ... a, s, p, // ... with all parameters unchanged p.match([${n}])  //     tests whether p contains any digit of n
||                 //     if it doesn't:
f(               //       do another recursive call with:
a,             //         a[] unchanged
s + n,         //         n added to s (as an integer)
p + n          //         n appended to p (as a string)
)                //       end of inner recursive call
)                    //   end of outer recursive call
:                      // else:
m = m > s ? m : s    //   this is a leaf node: update m to max(m, s)


Jelly,  12  11 bytes

-1 thanks to Nick Kennedy (use the implicit make_digits of Q to get rid of D)

ŒPQ€FQƑƊƇ§Ṁ


A monadic Link accepting a list of positive integers which yields the maximal sum of those subsets which repeat no decimal digits between elements.

Try it online!

How?

ŒPQ€FQƑƊƇ§Ṁ - Link: list of positive integers
ŒP          - power set
Ƈ   - filter keep those for which:
Ɗ    -   last three links as a monad:
Q€        -     de-duplicate each
F       -     flatten
Ƒ     -     is invariant under:
Q      -       de-duplication
§  - sum each
Ṁ - maximum

• You can drop the D: ŒPQ€FQƑƊƇ§Ṁ for 11 – Nick Kennedy May 24 '19 at 16:38
• Ah, yes I forgot that Q performs a call to iterable with make_digits=True. Thanks! – Jonathan Allan May 24 '19 at 18:00

Haskell, 81 76 bytes

_?[]=0
n?(a:b)|any(elemn)$show a=n?b|True=max(n?b)$a+(n++show a)?b
g=(""?)


Try it online!

Brachylog, 13 bytes

{⊇.dᵐc≠∧}ᶠ+ᵒt


Try it online!

Explanation

{     }ᶠ         Find all…
⊇.                subsets of the input…
dᵐ              …where each number with duplicate digits removed…
c≠∧           …has different digits from the others
+ᵒ     Order by sum
t    Tail (last element)

• @JonathanAllan Fixed at the cost of 2 bytes, thanks. – Fatalize May 24 '19 at 14:39
• You seem to output the list instead of the sum. – Emigna May 24 '19 at 16:58
• might not work for all the cases. – biziden May 26 '19 at 17:31

Python 2, 94 bytes

f=lambda l,r=[],S=set:l and max([f(l[1:],r+l[:1]),f(l[1:],r)][S(l[0])&S(r)>S():])or sum(r)


Try it online!

Python 3.8 (pre-release), 95 bytes

f=lambda l,r=[]:l and max([f(k:=l[1:],r+l[:1]),f(k,r)][bool({*str(l[0])}&{*str(r)}):])or sum(r)


Try it online!

Perl 5, 82 bytes

max(map{my$n=2*$_;my@t=grep{($n/=2)%2}@_;"@t"!~/(\d).* .*\1/?sum(@t):0}0..2**@_-1)  Try it online! With spaces: sub f { max( map { my$n = 2 * $_; my @t = grep {($n/=2)%2} @_;
"@t"!~/(\d).* .*\1/ ? sum(@t) : 0
}
0 .. 2**@_-1
)
}


Loops through all possible 2^n subarrays of the input array where each element either participates or not. Then for valid subarrays, those not matching the regex which finds common digits in other elements, use the sum of them and return the max of those valid sums.