4
\$\begingroup\$

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

\$\endgroup\$

closed as off-topic by manatwork, Xcali, Stephen, Arnauld, Jonathan Allan May 24 at 18:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – manatwork, Arnauld, Jonathan Allan
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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
\$\endgroup\$
  • \$\begingroup\$ Test Case 2: {121, 333, 4} = 458 \$\endgroup\$ – Jonathan Allan May 24 at 14:27
  • \$\begingroup\$ @JonathanAllan: Ah OK. Same digits in a number is okay. Fixed :) \$\endgroup\$ – Emigna May 24 at 14:43
1
\$\begingroup\$

Wolfram Language (Mathematica), 77 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ thanks for the solution, could you please explain, as I have limited knowledge of Wolfram Langauge. \$\endgroup\$ – biziden May 24 at 14:29
1
\$\begingroup\$

Python 2, 137 112 105 119 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!

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

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)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can drop the D: ŒPQ€FQƑƊƇ§Ṁ for 11 \$\endgroup\$ – Nick Kennedy May 24 at 16:38
  • \$\begingroup\$ Ah, yes I forgot that Q performs a call to iterable with make_digits=True. Thanks! \$\endgroup\$ – Jonathan Allan May 24 at 18:00
1
\$\begingroup\$

Haskell, 81 76 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ @JonathanAllan Fixed at the cost of 2 bytes, thanks. \$\endgroup\$ – Fatalize May 24 at 14:39
  • \$\begingroup\$ You seem to output the list instead of the sum. \$\endgroup\$ – Emigna May 24 at 16:58
  • \$\begingroup\$ might not work for all the cases. \$\endgroup\$ – biziden May 26 at 17:31
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.