# Minimum Subsequence Sum Algorithm Verification

I have an algorithm which is meant to solve the following computational problem:

Input: Sequence of positive integers
Output: A Sub-sequence of some desired length derived from original Sequence such that the sum of the sub-sequence’s elements are the minimum sum possible

The Algorithm I have to solve this problem is implemented as a method in Java:

``public int[] runA(int k) {          //k is desired length of sub-sequence          /*Sequence S is the original sequence provided as input, it is available as a class variable         for the class 'MinimumSubsequence' which this method 'runA' is apart of*/                                 //A is Sequence S copy with pseudo-boolean values attached to each element in S         int[][] A = new int[this.S.length][2];         //B is size K array storing the k smallest elements found in S along with their indexes         int[][] B = new int[k][2];          //initialization         for (int i = 0; i < this.S.length; i++) {             A[i][0] = this.S[i];             A[i][1] = False;         }         for (int i = 0; i < k; i++) {             B[i][0] = this.S[i];             B[i][1] = i;         }          //Execution         //search for k smallest elements in sequence S         for (int i = 0; i < k; i++) {             for (int j = 0; j < this.S.length; j++) {                 if (A[j][0] <= B[i][0] && A[j][1] == False) {                     B[i][0] = A[j][0];                     B[i][1] = j;                 }                 A[(B[i][1])][1] = True;             }         }          //build subsequence         int[][] C = new int[this.S.length][2];         for (int i = 0; i < C.length; i++) {             C[i][1] = False;         }         for (int i = 0; i < C.length; i++) {             for (int j = 0; j < B.length; j++) {                 if (B[j][1] == i && (C[i][1] == False)) {                     C[i][0] = B[j][0];                     C[i][1] = True;                 }             }         }         int[] D = new int[k];         int j = 0;         for (int i = 0; i < C.length; i++) {             if (C[i][1] == True) {                 D[j] = C[i][0];                 j++;             }         }          return D;     } ``

The algorithm basically works by scanning the original sequence provided, each time scanning for the next smallest number. Once it has found the k smallest numbers in the sequence it builds and returns a sub-sequence made from those smallest elements in the original sequence

I believe that this algorithm does correctly solve the computational problem and that the running time of this algorithm is in O(N) (N being size of input sequence). I would just like some verification about the correctness and efficiency of this algorithm. I am also wondering if there exists are more efficient algorithm to solve this computational problem as I’m just not very satisfied with this one but can think of no other approach.