pmcgee

Target Sum - return all sets [using Arrays]

Apr 14th, 2021 (edited)
504
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. program Project1array;
  2. {$APPTYPE CONSOLE}
  3. uses
  4.   System.SysUtils, Generics.Collections;
  5. //
  6. //  Generate a list of all sub-lists that sum to the target figure.
  7. //
  8.  
  9. type
  10.    TintArr = TArray< integer >;
  11.   TAintArr = TArray< TArray< integer > >;
  12.  
  13. //  --  --  --  --  --
  14.  
  15. function ArrPrepend( x : integer; A : TintArr): TintArr;
  16. begin
  17.   insert(x, A, 0);
  18.   ArrPrepend := A;
  19. end;
  20.  
  21. function ListAppend( A : TintArr; L : TAintArr): TAintArr;
  22. begin
  23.   insert(A, L, high(L)+1);
  24.   ListAppend := L;
  25. end;
  26.  
  27. //  --  --  --  --  --
  28.  
  29. function target_sum(const a : TintArr; const k,x : integer) : TAintArr;
  30. begin
  31.   if k > high(a) then begin
  32.                         //result := TAintArr.create();             //  []
  33.                         exit(0);
  34.                       end;
  35.  
  36.   if x = a[k]    then begin
  37.                         var single :=  TintArr.Create(a[k]);       //  [ a[k] ]
  38.                             result := TAintArr.create(single);     //  [ [a[k]] ]
  39.                         exit;
  40.                       end
  41.   else
  42.                       begin
  43.                         var s := target_sum(a, k + 1, x       );   // not using a[k]
  44.                         var t := target_sum(a, k + 1, x - a[k]);   //     using a[k]
  45.  
  46.                         for var i  := 0 to high(t) do              // high( [] ) = -1
  47.                             s := ListAppend( ArrPrepend(a[k],t[i]) ,s);
  48.                         result := s;
  49.                       end;
  50. end;
  51.  
  52. //  --  --  --  --  --
  53.  
  54. procedure print_list(const list : TintArr);
  55. begin
  56.   for var i in list do write(i, ', ');  writeln;
  57. end;
  58.  
  59. //  --  --  --  --  --
  60.  
  61. var
  62.   a :  TintArr;
  63.   s : TAintArr;
  64. const
  65.   target = 0;
  66.  
  67. begin
  68.   ReportMemoryLeaksOnShutdown := true;
  69.  
  70. //a := TintArr.Create(1,2,-1,-2);
  71.   a := TintArr.Create(1, 4, 5, 2, 7, 8, -3, -5, -6, 9, 3, -7, -1, 5, 6);
  72.   s := target_sum(a,0,target);
  73.  
  74.   write('Target = ', target, ' from : '); print_list(a);  writeln;
  75.  
  76.   if high(s) >0 then for var list in s do print_list(list)
  77.                 else writeln('x');
  78.   writeln;
  79.   writeln('# Solutions = ', high(s)+1);
  80.   writeln;
  81.  
  82.   readln;
  83. end.
  84.  
  85.  
  86.  
  87. (*  Javascript
  88.  
  89. function target_sum(a, k, x) {
  90.     if (k == a.length) return [];
  91.     if (a[k] == x) {
  92.         return [ [a[k]] ];
  93.     } else {
  94.         var s = target_sum(a, k + 1, x);        // not using a[k]
  95.         var t = target_sum(a, k + 1, x - a[k]); // using a[k]
  96.         for (var i = 0; i < t.length; ++i) {
  97.             t[i].unshift(a[k]);                 // a[k] is part of the solution
  98.             s.push(t[i]);                       // merge t[] into s[]
  99.         }
  100.         return s;
  101.     }
  102. }
  103.  
  104. var s = target_sum([1, 4, 5, 2, 7, 8, -3, -5, -6, 9, 3, -7, -1, 5, 6], 0, 0);
  105. for (var i = 0; i < s.length; ++i)
  106.     console.log(s[i].join(","));
  107.  
  108. *)
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×