returning all combination of index i,j in 2d vector that sum up to desired value

user_13403510 0
Viewed 399

I have a 2D vector v (all values are positive and the 2D matrix is a square matrix) and a given value k. For e.g.,

v={
   {2,1},
   {3,4}
  }

k = 3

I want to find and store all those combinations of i, j such that

arr[i] + arr[j] = k, or
arr[i] = k, or
arr[j] = k

For example v[0][0] + v[0][1] = 3 & v[1][0] = 3. I want to store the pairs in an array like this std::vector<std::vector<std::pair<int, int>>>.

Sample input:
v={
   {2,1},
   {3,4}
  }

k = 3

Sample output:
{{(0,0),(0,1)}, {(1,0)}}

Individual parts I worked by;

#include<iostream>
#include<vector>
int main(){
    using namespace std;
    vector<vector<int>>v={{2,1},{3,4}};
    vector<pair<int,int>>k;
    int size=v.size();
    for(size_t i=0;i<size;i++){
        for(size_t j=0;j<size;j++){
            if(v[i][j]==3){
                k.push_back(make_pair(i,j));
            }     
        }
    }
}

Edit link for actual questions which I perceived and tried to solve in the above mentioned way.

vector dictionary stl algorithm c++
2 Answers

Edit

The first answer I gave was considering any number of elements can be chosen to form the target sum. But since we can take only 2 atmost, here's an edit.

In case when two elements form the target sum, the gist is that when you input an element x, if we had already inputted y = target - x element in the past, pair x with all the occurances of y.

Here's the code which should be straightforward to follow.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, pii> PIJ;

int main() {
    int N, target;
    cin >> N >> target;

    vector<vector<int>> matrix(N, vector<int>(N));
    unordered_map<int, vector<pii>> M;
    vector<PIJ> res;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            int x;
            cin >> x;

            matrix[i][j] = x;

            int y = target - x;
            for (const pii& p: M[y])
                res.emplace_back(p, make_pair(i, j));

            M[x].emplace_back(i, j);
        }
    }
}

Consider the problem in 1-D of length n first. The most naive algorithm would be to form all 2^n-1 combinations and check for each if it's elements sum up to target.

Luckily, the same search space can be exhausted by another algorithm which follows optimal substructure property. Let count(i, t) represent the total number of combinations of first i elements which sum up to t. Then count(i, t) = count(i-1, t-arr[i]) + count(i-1, t). The base condition will be when t = 0. If 0 can be present in the input array then you will have to take that into consideration. There will be overlapping subproblems which calls for dynamic programming.

Keep a running array chosen and everytime you choose a value (when calling count(i-1, t-arr[i])), push the index into chosen and if you reach the base condition, push copy of chosen into your say combinations array. When the control returns back to where you called count(i-1, t-arr[i]), pop this value off chosen.

Your 2-D problem can be converted into 1-D array of pair<int, int> and same algorithm can be applied.

user_33021150

The loop in your example only finds pairs {i,j} where v{i,j} == k. If you also want to include all combinations { {i1,j1}, {i2, j2} } that is quite a different search.

The problem with your Sample output { { (0,0), (0,1) }, { (1,0) } } is that they are different sizes. If its type is

std::vector < std::vector < std::pair < int, int > > >

then how long is the vector of pairs allowed to be? If all values of v were 1 would the solution then be { { (0,0), (0,1), (1,0) }, { (0,0), (0,1), (1,1) }, { (0,0), (1,0), (1,1) }, { (0,1), (1,0), (1,1) }, }?

As @RisingStark comments, the most straightforward way to run this is to have an iteration over the allowed number of pairs. Which stops being trivial after 2.

Some examples for the case of 2 are here. For the subset-sum problem there is no general efficient solution.

user_17939680
Related