C# DFS Solution


  • 0
    T
    public class Solution {
        int result = 0;
        public int ShoppingOffers(IList<int> price, IList<IList<int>> special, IList<int> needs) {
            int len = price.Count;
            result = 0;
            for(int i = 0;i<len;i++){
                result += price[i]*needs[i];
            }
            
            Helper(price,special,needs,0,special.Count,len,result);
            
            return result;
        }
        
        private void Helper(IList<int> price, IList<IList<int>> special, IList<int> needs,int index, int offLen,int len,int total){
            for(int i = index;i<offLen;i++){
                bool valid = true;
                for(int j = 0;j<len;j++){
                    if(needs[j] < special[i][j]){
                        valid = false;
                        break;
                    }
                }
                
                if(valid){
                    int nextTotal = total;
                    for(int j = 0;j<len;j++){
                        needs[j]-=special[i][j];
                        nextTotal-=price[j]*special[i][j];
                    }
                    nextTotal+=special[i][len];
                    
                    result = Math.Min(result,nextTotal);
                    
                    Helper(price,special,needs,i,offLen,len,nextTotal);
                    
                    for(int j = 0;j<len;j++){
                        needs[j]+=special[i][j];
                    }
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.