CODEWITHSUNDEEP
c++vector
Allanqunzi
Allanqunzi

Reputation: 3260

segmentation fault on vector

I have a piece of code which uses the DFS algorithm for solving the subset problem in Leetcode. The problem is stated as below.

Given a set of distinct integers, S, return all possible subsets.

Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.

For example, If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

my c++ code is as below, the problem is that it outputs "=======", but after that it says "segmentation fault". I don't really get this segmentation fault error. Can someone tell me which part of the code is wrong?

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

class Solution
{
public:
    //Solution();
    //~Solution();
    std::vector< std::vector<int>  > subset(std::vector<int> S){
        sort(S.begin(), S.end());
        std::vector< std::vector<int> > res;
        std::vector<int> temp;
        res.push_back(temp);
        dfs(res, temp, S, 0);

        return res;
    }

private:
    void dfs(std::vector<std::vector<int> > res, std::vector<int> temp,     std::vector<int> S, int pos){
        for (int i = pos; i <= S.size()-1; i++)
        {
        temp.push_back(S[i]);
        res.push_back(temp);
        dfs(res, temp, S, i+1);
        temp.pop_back();                    /* code */
        }
    }

        /* data */
    };


std::vector<int> array(3);
array[0]=1; array[1]=2; array[2]=3;
std::vector<std::vector<int> > res;
Solution MySolution;
res=MySolution.subset(array);

cout<<"======="<<endl;
cout<<res[0][0]<<endl;

     return 0;
}

Upvotes: 0

Views: 668

Answers (2)

Suedocode
Suedocode

Reputation: 2534

You are passing copies of vectors, not vector references.

    std::vector< std::vector<int> > res;
    std::vector<int> temp;
    res.push_back(temp);
    dfs(res, temp, S, 0);

This code creates a vector<vector<int>> res;, pushes an empty vector to it, then calls a function that does not change any state within this scope. Finally, you then de-reference with res[0][0]. res[0] gives an empty vector, so then the second [0] segfaults.

Replace this function definition:

void dfs(std::vector<std::vector<int>> res, std::vector<int> temp, std::vector<int> S, int pos){...}

With this:

void dfs(std::vector<std::vector<int>>& res, std::vector<int>& temp, const std::vector<int>& S, int pos){...}

Upvotes: 2

yizzlez
yizzlez

Reputation: 8805

dfs(res, temp, S, i+1);, is almost certainly the source of your problem. On the last iteration, i+1 == S.size() resulting in a segmentation fault. An easy fix is:

for (int i = pos; i <= S.size()-2; i++)

Upvotes: 1

Related Questions