Finding sum of sub vector satisfying inequality I am asked to implement code that checks if there is a sub vector that has a sum, v_l, that would satisfy \$ \frac{1}{4}mn + 1 \leq v_l \leq v - \frac{1}{4} m n - 1\$.

def possible(vec, m):
    n = len(vec)     # Number of columns
    v = sum(vec)
    global R

    R = []

    num = {i: 0 for i in set(vec)}
    for i in vec:
        num[i] += 1

    solution = dfs_backtrack(num, m, n, v)    

return solution

def dfs_backtrack(vec, m, n, v):

    v_l = sum([i*vec[i] for i in vec.keys()])
    R.append(vec)

    if 0.25 * m * n + 1 &lt;= v_l &lt;= v - 0.25 * m * n - 1:
        return vec

    for i in vec.keys():
        temp = dict(vec)
        temp[i] -= 1
        if temp[i] is 0:
            temp.pop(i)
        if temp and temp not in R :
            temp = dfs_backtrack(temp, m, n, v)
        else:
            temp = None
        if temp:
            return temp
    return None


From my analysis it would have a space and time complexity of \$O(n^{m+1} m^{-m-1})\$, where \$1 \leq m \leq n\$. What can I do to improve the space and time complexity?
Since the sum v_l changes with each iteration through your dictionary values of num, I don't know of a way to pre-compute the right-side sums before-hand. This would be a little easier if you could use external modules. That said, you might see a slight speed-up if you use more comprehensions. For example, you can get num via num = {x : vec.count(x) for x in vec}. Also, use == 0 (not is 0) to check zero equality and use is None(not == None) to check None.

Also, you are iterating through all possible combinations. In the case of using votes1 and m1, you know that m = m1 = 10 and n = len(votes1) = 30. So you know that your lower bound is cut-off at 76. Those are 76 permutations that you do not need to use. You can include a break statement at the lower bound since you are incrementing downward (temp[i] -= 1), but I would instead use this lower bound as the starting point and iterate by incrementing upward as you may find some other way to restrict the sums in the upper limit. 

Lastly, the use of globals and non-descriptive variable names makes it hard to edit the code. For example, votes instead of vec, ndict instead of n, etc. Also, you can pass R into dfs_backtrack. 

I personally prefer iterating over lists instead of dictionaries since you can use zip. I don't have a full solution for your problem, but it may help as a start.

def get_lower_bound(m, n):
    return m*n/4 + 1

def get_upper_bound(m, n, v):
    return v - m*n/4 - 1

def initialize_constants(m, n, votes):
    """ Pre-compute these values as they do not change."""
    size = len(votes)
    total = sum(votes)
    lower_bound = get_lower_bound(m, n=30)
    return size, total, lower_bound

def initialize_vl(votes, m):
    ## I think set look-ups are quickest, these provide unique values just like dictionaries do
    unique_votes = list(set(votes)) #keys for num
    vcounts = [votes.count(x) for x in unique_votes] #vals for num
    vl = sum([a*b for a,b in zip(unique_votes, vcounts)])
    return unique_votes, vcounts, vl


This way, you don't need to use 

    temp = dict(vec)
    temp[i] -= 1
    if temp[i] is 0:
        temp.pop(i)
    if temp and temp not in R :


as you are creating temp as a copy of vec; any change to temp changes vec as well. Also, you can iterate through your unique values in list(set(...)) instead of checking if each element is in R.

Sorry I could not be of more help. Let me know if anything is unclear.